已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

算法如下：

1. 设置两个指针p1和p2分别指向S1和S2的头节点。
2. 创建一个新链表S3，设置一个指针p3指向S3的头节点。
3. 循环遍历S1和S2，比较p1指向的节点和p2指向的节点的值，如果相等，则将该节点加入S3中，同时p1和p2都向后移动一位；如果不相等，则将值较小的指针向后移动一位。
4. 循环结束后，返回S3。

Python代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def intersection(S1: ListNode, S2: ListNode) -> ListNode:
    p1, p2 = S1, S2
    dummy = ListNode(0)
    p3 = dummy
    while p1 and p2:
        if p1.val == p2.val:
            p3.next = ListNode(p1.val)
            p3 = p3.next
            p1 = p1.next
            p2 = p2.next
        elif p1.val < p2.val:
            p1 = p1.next
        else:
            p2 = p2.next
    return dummy.next

相关问题

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3

好的，让我看看可以为您服务！关于您的第一个问题，可以使用双指针来解决。首先，我们需要新建一个链表用于存储交集。然后，我们使用两个指针分别指向两个链表的头节点，并比较它们的值。如果两个值相同，则将该值添加到新链表中。如果S1当前节点的值小于S2当前节点的值，则S1向后移动一个节点，反之，则S2向后移动一个节点。直到一个链表遍历完成，则停止遍历。最终，新建的链表S3即为S1与S2的交集。

以下是C++代码实现：

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

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* res = new ListNode(0);
    ListNode* cur = res;
    while (headA != NULL && headB != NULL) {
        if (headA->val == headB->val) {
            cur->next = new ListNode(headA->val);
            cur = cur->next;
            headA = headA->next;
            headB = headB->next;
        } else if (headA->val < headB->val) {
            headA = headA->next;
        } else {
            headB = headB->next;
        }
    }
    return res->next;
}

注意：这个函数不会判断S1与S2是否为非降序链表序列，需要在调用该函数前自己先进行判断。

已知两个非降序链表序列s1与s2，设计函数构造出s1与s2的交集新链表s3

### 回答1：
可以使用双指针法来解决这个问题。定义两个指针p1和p2分别指向s1和s2的头节点，然后比较p1和p2节点的值，如果相等，则将该节点加入新链表s3中，并将p1和p2指针同时向后移动一位；如果p1节点的值小于p2节点的值，则将p1指针向后移动一位；如果p1节点的值大于p2节点的值，则将p2指针向后移动一位。直到p1或p2指针为空为止，此时s3就是s1和s2的交集新链表。

具体实现可以参考以下代码：

struct ListNode* getIntersection(struct ListNode* s1, struct ListNode* s2) {
    struct ListNode* p1 = s1;
    struct ListNode* p2 = s2;
    struct ListNode* s3 = NULL;
    struct ListNode* tail = NULL;

    while (p1 && p2) {
        if (p1->val == p2->val) {
            struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
            node->val = p1->val;
            node->next = NULL;

            if (s3 == NULL) {
                s3 = node;
                tail = node;
            } else {
                tail->next = node;
                tail = node;
            }

            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->val < p2->val) {
            p1 = p1->next;
        } else {
            p2 = p2->next;
        }
    }

    return s3;
}

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

由于两个链表是非降序的，那么可以考虑使用双指针的方法。分别用指针p1和p2指向两个链表的表头，然后比较p1和p2对应的节点的大小。

1. 如果p1节点的值小于p2节点的值，那么将p1往后移动一位。

2. 如果p1节点的值大于p2节点的值，那么将p2往后移动一位。

3. 如果p1节点的值等于p2节点的值，那么将p1和p2都往后移动一位，并将该节点的值加入到新链表中。

代码实现：

C++代码如下：

#include<iostream>
using namespace std;

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

ListNode* getIntersection(ListNode* headA, ListNode* headB) {
    ListNode* p1 = headA;
    ListNode* p2 = headB;
    ListNode* res = new ListNode(-1);  // 新链表
    ListNode* p3 = res;

    while (p1 != NULL && p2 != NULL) {
        if (p1->val < p2->val) {
            p1 = p1->next;
        } else if (p1->val > p2->val) {
            p2 = p2->next;
        } else {
            p3->next = new ListNode(p1->val);
            p1 = p1->next;
            p2 = p2->next;
            p3 = p3->next;
        }
    }

    p3 = res->next;
    delete res;   // 释放内存
    return p3;
}

int main() {
    ListNode* a1 = new ListNode(1);
    ListNode* a2 = new ListNode(2);
    ListNode* a3 = new ListNode(3);
    ListNode* a4 = new ListNode(4);
    a1->next = a2;
    a2->next = a3;
    a3->next = a4;

    ListNode* b1 = new ListNode(2);
    ListNode* b2 = new ListNode(4);
    ListNode* b3 = new ListNode(6);
    b1->next = b2;
    b2->next = b3;

    ListNode* res = getIntersection(a1, b1);
    while (res != NULL) {
        cout << res->val << " ";
        res = res->next;
    }

    return 0;
}

Python代码如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1: ListNode
        :type head2: ListNode
        :rtype: ListNode
        """
        p1 = headA
        p2 = headB
        res = ListNode(-1)
        p3 = res

        while p1 is not None and p2 is not None:
            if p1.val < p2.val:
                p1 = p1.next
            elif p1.val > p2.val:
                p2 = p2.next
            else:
                p3.next = ListNode(p1.val)
                p1 = p1.next
                p2 = p2.next
                p3 = p3.next
        
        p3 = res.next
        del res
        return p3

时间复杂度：

由于要遍历两个链表，时间复杂度为O(m+n)，其中m和n分别是两个链表的长度。

空间复杂度：

因为要构造一个新链表，所以空间复杂度为O(min(m,n))，其中m和n分别是两个链表的长度。

### 回答3：
解题思路：

由于s1与s2都是非降序链表序列，因此可以考虑从头开始比较s1和s2的元素，并将相同的元素加入到新链表s3中。具体来说，可以定义两个指针p1和p2分别指向s1和s2的头结点，不断地比较它们的元素大小，将相同的元素加入到s3中，并将指针p1和p2往后移动，直至其中一个链表遍历完。代码如下所示。

代码实现：

struct ListNode* getIntersectionNode(struct ListNode* s1, struct ListNode* s2) {
struct ListNode dummy; // 定义头结点
struct ListNode* tail = &dummy; // 定义尾指针
struct ListNode *p1 = s1, *p2 = s2;

while (p1 && p2) { // 当两个链表都没有遍历完时
if (p1->val == p2->val) { // 相同元素
tail->next = p1; // 将相同元素加入到新链表s3中
tail = p1; // 更新尾指针
p1 = p1->next;
p2 = p2->next;
} else if (p1->val < p2->val) { // s1元素小，p1向后移动
p1 = p1->next;
} else { // s2元素小，p2向后移动
p2 = p2->next;
}
}

tail->next = NULL; // 最后一个元素指向NULL，表示结束
return dummy.next; // 返回新链表s3的头结点
}

时间复杂度：

每次移动p1或p2后，至少有一个指针会指向下一个不同的元素，因此时间复杂度为O(m+n)，其中m和n分别为s1和s2的长度。

空间复杂度：

只需要定义常数个指针变量和一个头结点，因此空间复杂度为O(1)。