skip to content

Search

160相交链表

1 min read Updated:

相交链表题解

题目:

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

双指针

双指针算法本质上就是a+b=b+aa + b = b + a的问题

pApA先走A再走B,pBpB先走B再走A,两者里程都相等。由于两条链表最后有公共部分,所以pApA和pBpB最后会在相交部分相等

双指针

长度差

长度差是一个更直观的方法

剪掉长链表的前面部分,使得两条链表长度相等,然后同时遍历两条链表,找到第一个相同的节点就是相交节点