【LeetCode】160. 相交链表

160. 相交链表（简单）

题解

• 对于这道题，首先要理解题意：如果两个单链表会相交，那么返回相交的起始节点；否则返回 null。 无需看“自定义评测”部分。

• 假设链表 A 的头节点到相交点的距离为 a，链表 B 的头节点到相交点的距离为 b，相交点到链表终点的距离为 c。

• 我们使用两个指针分别指向两个链表的头节点（这里不能直接移动头节点，因为循环的时候还需要用到头节点，因此头节点不能改变），并以相同的速度前进，如果到达链表结尾，则移动到另外一条链表的头节点继续前进。按照这种前进方法，两个指针会在 a+b+c 次前进后到达相交节点。

• 为什么是 a+b+c 次呢?

  若相交，链表A： a+c，链表B : b+c。
  因为 a+c+b+c = b+c+a+c ，所以 a+c+b = b+c+a，则会在公共处 c 起点相遇。若不相交，即 c=0，则 a+b = b+a 。因此相遇处是NULL。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *ptrA = headA, *ptrB = headB;
        while(ptrA != ptrB){
            // 如果ptrA不为空，说明链表A还没有遍历结束，遍历下一个节点
            // 如果为空，说明已经遍历到链表A的终点，移动到链表B继续遍历
            ptrA = ptrA ? ptrA->next : headB;
            ptrB = ptrB ? ptrB->next : headA;
        }
        return ptrA;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13