两个有序链表序列的交集

一、问题描述

给定两个有序链表，要求找出这两个链表的交集元素，并以有序链表的形式返回。

二、思路

1. 双指针法：使用两个指针分别指向两个链表的当前节点。
2. 比较元素：
   • 如果两个指针指向的元素相等，则将该元素加入结果链表，并移动两个指针。
   • 如果指针A指向的元素小于指针B指向的元素，则移动指针A，反之亦然。
3. 结束条件：当任一链表的指针到达末尾时停止。

三、算法步骤

1. 初始化两个指针 pA 和 pB 分别指向链表A和链表B的头节点。
2. 初始化一个空的结果链表 result。
3. 遍历两个链表，比较 pA 和 pB 指向的节点：
   • 如果 pA.val == pB.val，将该值添加到 result，然后同时移动 pA 和 pB。
   • 如果 pA.val < pB.val，移动 pA。
   • 如果 pA.val > pB.val，移动 pB。
4. 返回结果链表。

四、示例代码（Python）

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef getIntersection(headA, headB):dummy = ListNode(0)  # 哨兵节点tail = dummy  # 结果链表的尾节点pA, pB = headA, headBwhile pA and pB:if pA.val == pB.val:tail.next = ListNode(pA.val)  # 添加交集元素tail = tail.nextpA = pA.nextpB = pB.nextelif pA.val < pB.val:pA = pA.nextelse:pB = pB.nextreturn dummy.next  # 返回交集链表

五、复杂度分析

• 时间复杂度：O(m + n)，其中 m 和 n 分别为链表A和链表B的长度。
• 空间复杂度：O(1)（如果不考虑结果链表的存储）。

六、总结

通过使用双指针法，可以高效地找出两个有序链表的交集元素。该方法不仅简单易懂，而且具有较好的时间和空间性能。理解这一方法对于处理有序数据结构的交集问题非常重要。