力扣160.相交链表

题目描述

难度：简单

示例

思路

使用双指针

使用指针分别指向两个不同的链表进行比较

解题方法

1.首先进行非空判断

2.初始化指针分别指向两个链表

3.遍历链表

while (pA != pB)：

当pA和pB不相等时，继续循环。如果pA和pB相等，说明找到了相交的节点，或者两个链表不相交，pA和pB都为null。

pA = pA == null ? headB : pA.next：

如果pA为null，说明已经遍历完链表A，接下来从链表B的头节点开始继续遍历。

如果pA不为null，则移动到链表A的下一个节点。

pB = pB == null ? headA : pB.next：

如果pB为null，说明已经遍历完链表B，接下来从链表A的头节点开始继续遍历。

如果pB不为null，则移动到链表B的下一个节点。

4.return pA返回结果

为什么有效

假设链表A的长度为L1，链表B的长度为L2，相交部分的长度为C，不相交部分的长度分别为L1 - C和L2 - C。

总移动距离：

pA的总移动距离为L1 + L2。

pB的总移动距离为L2 + L1。

两个指针的总移动距离相同，都是L1 + L2。

相遇点：

如果两个链表有交点，pA和pB最终会在交点处相遇。

如果两个链表没有交点，pA和pB最终都会遍历完两个链表，同时变为null，退出循环。

java代码

力扣官方题解+个人注解：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//非空判断if(headA == null || headB == null){return null;}//初始化指针ListNode pA = headA, pB = headB;//遍历链表while(pA != pB){pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}