已知两个非降序链表序列s1与s2，设计函数构造出s1与s2的交集新链表s3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出null。

### 回答1：
算法思路：

1. 定义两个指针分别指向两个链表的头结点，比较两个指针所指节点的值，将较小值的指针向后移动一位。

2. 如果两个指针所指节点的值相等，则将该节点的值加入新链表，并将两个指针都向后移动一位。

3. 重复上述步骤，直到其中一个链表遍历完毕。

4. 如果新链表为空，则输出null，否则输出新链表的值。

Python 代码实现：

# 定义链表节点类
class ListNode:
    def __init__(self, val=, next=None):
        self.val = val
        self.next = next

# 定义函数构造出两个链表的交集新链表
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 定义新链表的头结点和尾结点
    dummy = ListNode()
    tail = dummy

    # 定义两个指针分别指向两个链表的头结点
    p1, p2 = headA, headB

    # 遍历两个链表，比较节点的值
    while p1 and p2:
        if p1.val < p2.val:
            p1 = p1.next
        elif p1.val > p2.val:
            p2 = p2.next
        else:
            # 如果两个节点的值相等，则将该节点的值加入新链表
            tail.next = ListNode(p1.val)
            tail = tail.next
            p1 = p1.next
            p2 = p2.next

    # 如果新链表为空，则输出null，否则输出新链表的值
    if dummy.next is None:
        return "null"
    else:
        return dummy.next.val

# 读入两个非降序链表
s1 = list(map(int, input().split()))
s2 = list(map(int, input().split()))

# 构造两个链表
headA = ListNode(s1[])
p1 = headA
for i in range(1, len(s1)):
    if s1[i] == -1:
        break
    node = ListNode(s1[i])
    p1.next = node
    p1 = node

headB = ListNode(s2[])
p2 = headB
for i in range(1, len(s2)):
    if s2[i] == -1:
        break
    node = ListNode(s2[i])
    p2.next = node
    p2 = node

# 构造交集新链表
s3 = getIntersectionNode(headA, headB)

# 输出交集新链表
print(s3)

### 回答2：
题目中要求我们输入两个非降序的链表，并将它们的交集构造为一个新链表输出。我们可以从链表的基本操作和链表的遍历两个方面来解决这个问题。

对于链表的基本操作，我们需要先定义一个链表节点的结构体，并实现链表的初始化、插入和删除等操作。

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

ListNode* createList() {
ListNode *head = new ListNode(-1);
return head;
}

void insertNode(ListNode *head, int val) {
ListNode *node = new ListNode(val);
node->next = head->next;
head->next = node;
}

void deleteNode(ListNode *head, ListNode *node) {
ListNode *prev = head;
while (prev->next != node) {
prev = prev->next;
}
prev->next = node->next;
delete node;
}

对于链表的遍历，我们可以使用两个指针分别指向两个链表的开头，然后进行比较。如果两个节点的值相等，就将这个节点插入到新链表中；否则，将值较小的节点指针往下移动一个节点。当其中一个链表已经遍历完毕，就退出循环并输出新链表。

ListNode* intersection(ListNode *s1, ListNode *s2) {
ListNode *cur1 = s1->next, *cur2 = s2->next;
ListNode *s3 = createList();
while (cur1 != NULL && cur2 != NULL) {
if (cur1->val == cur2->val) {
insertNode(s3, cur1->val);
cur1 = cur1->next;
cur2 = cur2->next;
} else if (cur1->val < cur2->val) {
cur1 = cur1->next;
} else {
cur2 = cur2->next;
}
}
if (s3->next != NULL) {
return s3->next;
} else {
return NULL;
}
}

最后，我们可以在主函数中实现输入两个链表，调用intersection函数，输出新链表。

int main() {
ListNode *s1 = createList();
ListNode *s2 = createList();
int val;
while (cin >> val && val != -1) {
insertNode(s1, val);
}
while (cin >> val && val != -1) {
insertNode(s2, val);
}
ListNode *s3 = intersection(s1, s2);
if (s3 == NULL) {
cout << "null" << endl;
return 0;
}
ListNode *cur = s3;
while (cur != NULL) {
cout << cur->val;
cur = cur->next;
if (cur != NULL) {
cout << " ";
}
}
cout << endl;
return 0;
}

### 回答3：
算法思路：

我们可以使用双指针来遍历两个链表，每次比较两个指针所指的元素大小，若相等则加入新链表并将两个指针同时后移，若不相等则将指向小的元素的指针后移。

若其中一个链表已经遍历完，则结束循环，返回新链表。若新链表为空，则输出“null”。

参考代码：