链表相交问题如何通过双指针法解决？

本文共计974个文字，预计阅读时间需要4分钟。

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

def get_intersection_node(headA, headB): def get_length(head): length=0 while head: length +=1 head=head.next return length

lenA, lenB=get_length(headA), get_length(headB)

if lenA > lenB: for _ in range(lenA - lenB): headA=headA.next else: for _ in range(lenB - lenA): headB=headB.next

while headA and headB: if headA==headB: return headA headA=headA.next headB=headB.next

return None

示例创建两个链表node1=ListNode(1)node2=ListNode(2)node3=ListNode(3)node4=ListNode(4)node5=ListNode(5)

链表A: 1 -> 2 -> 3 -> 4node1.next=node2node2.next=node3node3.next=node4

链表B: 1 -> 2 -> 5node1.next=node2node2.next=node5

获取相交节点intersection_node=get_intersection_node(node1, node2)if intersection_node: print(fIntersection at node with value: {intersection_node.val})else: print(No intersection)

力扣题目链接

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null （no Intersected）。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为[0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

！！有没有人第一反应想到的是比较两个链表的值是否相等，相等的部分就是相交咯？？。。。No！咱就是一个大大的NO！大错特错！！

思路

我们应该比较的是地址是否相等，而不是值！！

假设：A链表中除了相交部分，其长度为x；B链表中除了相交部分，其长度为y；两链表相交部分长度为z

情况一：

如果相交，那么肯定有x+z+y=y+z+x；（为什么这里用到了z？？肯定是因为这是相交情况嘛！单从长度看，当然可以说x+y=y+x，但是在有相交的情况下，指针是要对整个链表遍历来寻找相交点，但是由于存在另一条链表比较短，当短的链表指针已经走到相交点时，长的链表指针还没走到。为了避免这个错开，谁先走完本身的长度谁就继续走另一条链表的路线。比如上面的示例：A的路线是（0-9-1-2-4-3-2-4），B的路线是（3-2-4-0-9-1-2-4）。到这里！！我们就能发现，只要相交，肯定存在移动x+z+y或y+z+x后下一步必定是相交的点！！！！！

情况二：

没有相交，那么x+y=y+x；为什么用x+y=y+x？？因为没有交点嘛。指针走完两条链表的长度最后发现没有交点，指针都会指向NULL；

结合两种情况，可以写出如下代码（C）：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *A=headA; struct ListNode *B=headB; //遍历完完本身的链表，就继续另一条链表。如果发现指针相等的情况就结束循环 while(A!=B){ A=A==NULL?headB:A->next; B=B==NULL?headA:B->next; } return A; //return B也可以 }

如有说的不对或者看不懂的地方，欢迎评论区留言~