7-52 两个有序链表序列的交集 (20 分)

### 回答1：
可以使用链表来实现。链表是一种由节点组成的数据结构，每个节点包含一个数据域和一个指向下一个节点的指针。在这个问题中，可以创建两个链表，分别表示7和52这两个数字，然后将它们依次相连形成一个新的链表，即可得到一个序列。具体实现可参考以下代码：

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

def create_linked_list(arr):
head = Node(arr[0])
tail = head
for i in range(1, len(arr)):
node = Node(arr[i])
tail.next = node
tail = node
return head

def merge_linked_list(head1, head2):
if not head1:
return head2
if not head2:
return head1
if head1.val <= head2.val:
head1.next = merge_linked_list(head1.next, head2)
return head1
else:
head2.next = merge_linked_list(head1, head2.next)
return head2

def print_linked_list(head):
while head:
print(head.val, end=' ')
head = head.next

arr1 = [7, 8, 9]
arr2 = [5, 2]
head1 = create_linked_list(arr1)
head2 = create_linked_list(arr2)
head = merge_linked_list(head1, head2)
print_linked_list(head) # 输出结果为：2 5 7 8 9

### 回答2：
题目描述：

给定两个升序链表 A 和 B，输出它们的交集。例如，链表 A，B 分别为： A = {1, 3, 4, 5, 7}，B = {2, 3, 5, 6, 9}，输出的交集为 {3, 5}。

解题思路：

这道题目非常适合使用双指针的解法，我们可以将指针分别指向链表 A 和链表 B 的头结点，然后开始比较这两个指针节点的大小，如果两个值相等，那么这个值就是两个链表的交集中的一个元素，将其记录下来，并分别向后移动指针 A 和指针 B，继续比较下一个节点的值，而如果节点的值不相等，那么就将值较小的指针向后移动一位，因为链表已经是升序排列的，如果值较小的指针向后移动一位，那么下一个元素的值不可能比值较大的指针的当前元素的值更小。

代码实现：

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}

ListNode* p1 = headA;
ListNode* p2 = headB;
ListNode* res = new ListNode(0);
ListNode* cur = res;

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

return res->next;
}

总结：

本题运用了双指针的思路，即用指针分别指向链表 A 和链表 B 的头结点，根据节点的大小关系来判断指针应该向哪里移动。因为链表是升序排列的，所以每次移动指针都可以排除一些不可能成为交集元素的节点，时间复杂度为 O(m + n)，其中 m 表示链表 A 的长度，n 表示链表 B 的长度。

### 回答3：
题目描述：

给定两个按非递减顺序排序的链表序列，求它们的交集。例如链表1：1→2→3→3→4→5→6，链表2：3→3→5→7，它们的交集为3→3→5。

分析：

由于两个链表都是按照非递减顺序排列的，因此可以利用双指针的方法，同时遍历两个链表。具体步骤如下：

1.初始化指向链表1和链表2的指针，分别为p1和p2。

2.遍历两个链表，当p1和p2指向的节点值相等时，将这个值加入结果链表中，并将p1和p2都向后移动一位；否则，将p1和p2中值较小的那个指针向后移动一位。

3.重复执行步骤2，直到一个链表遍历完毕，或者结果链表已经包含了所有的交集元素。

4.返回结果链表。

代码实现：

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        dummy = ListNode(0)
        p = dummy
        p1, p2 = headA, headB
        
        while p1 and p2:
            if p1.val == p2.val:
                p.next = ListNode(p1.val)
                p = p.next
                p1 = p1.next
                p2 = p2.next
            elif p1.val < p2.val:
                p1 = p1.next
            else:
                p2 = p2.next
        
        return dummy.next

总结：

本题使用了双指针的思想，时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。需要注意的一点是，由于链表中可能存在重复元素，因此需要在结果链表中保留这些重复的元素。