已知两个非降序链表序列S1和S2，设计算法实现S1与S2的交集操作

已知两个非降序链表序列S1和S2，设计算法实现S1与S2的交集操作。可以使用双指针的方法来实现这个操作。初始化两个指针分别指向S1和S2的头节点，然后比较指针所指向的节点的值，如果两个节点的值相等，则将该值加入到交集序列中，并将两个指针都向后移动一位；如果两个节点的值不相等，则将值较小的节点的指针向后移动一位。重复以上步骤直到其中一个链表遍历完毕。最后返回交集序列即可。

相关问题

已知两个非降序链表序列s1与s2，设计算法实现s1与s2的交集操作。

### 回答1：
可以使用双指针的方法，分别遍历s1和s2，比较当前指向的元素大小，如果相等则加入交集中，否则将指向较小元素的指针向后移动一位，直到其中一个链表遍历完为止。时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。

### 回答2：
交集操作是指求出两个集合中共有的元素。对于两个非降序链表序列s1和s2，我们可以使用双指针的方法来实现求交集操作。

我们可以定义两个指针p1和p2，分别指向s1和s2的头节点。然后对于每一个节点，我们比较它们的值，如果p1指向的节点的值小于p2指向的节点的值，则将p1向后移动一位；反之，如果p2指向的节点的值小于p1指向的节点的值，则将p2向后移动一位；否则，将当前节点的值加入到结果链表中，并将p1和p2同时向后移动一位。

这个算法的时间复杂度为O(m+n)，其中m和n分别为s1和s2的长度。因为我们每次移动的时候，最多只会移动一次p1或p2，所以移动的次数最多为m+n次。

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

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

ListNode* intersection(ListNode* s1, ListNode* s2) {
    ListNode dummy(0);
    ListNode* cur = &dummy;

    ListNode* p1 = s1;
    ListNode* p2 = s2;

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

    return dummy.next;
}

在这个实现中，我们使用了一个哑节点dummy来简化代码。在求交集操作的过程中，我们用cur指针来维护结果链表的尾部，并不断将新的节点加入到结果链表中。

注意，在上面的代码中，我们将节点的值复制了一份，并用它来构造新的节点。这是为了避免修改s1和s2的原始值。

总之，使用双指针的方法可以很高效地求出两个非降序链表序列的交集。

### 回答3：
首先需要了解什么是非降序链表。非降序链表也被称为升序链表，是一种特殊的链表，它的每个节点都比它的前一个节点大或者相等。因此，给定两个非降序链表s1和s2，找出它们的交集其实就是找出它们之间相同的元素。

实现该算法的一种简单方法是使用双指针。假设两个链表分别为s1和s2，设定指针p1指向s1的头结点，指针p2指向s2的头结点。同时移动两个指针，比较它们指向的节点的值。

情况一：如果p1所指节点的值小于p2所指节点的值，则移动p1指向链表的下一个节点，继续比较下一个节点与p2节点的值。

情况二：如果p1所指节点的值大于p2所指节点的值，则移动p2指向链表的下一个节点，继续比较下一个节点与p1节点的值。

情况三：如果p1所指节点的值等于p2所指节点的值，则将它加入交集链表中，然后同时移动p1和p2指向下一个节点，继续比较它们指向的节点的值。

当p1或p2中任意一个指针到达链表的末尾时，表示已经找到了交集链表中的所有节点。将交集链表返回作为结果即可。

该算法的时间复杂度为O(m+n)，其中m和n分别为两个非降序链表的长度。因为该算法只需要遍历一次每个链表，所以可以保证它的时间复杂度是线性的。

已知两个非降序链表序列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)。