已知两个非降序链表序列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++代码如下： ```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代码如下： ```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)。