问题描述：

给定两条链表的头结点headA, headB，判断这两条链表是否相交，如果相交找出相交开始的节点。

方法一

两个指针pA、pB分别遍历两条链表至尾节点（不是尾结点的下一个节点null）并统计节点数lenA、lenB，如果最后pA == pB，则说明链表相交，否则，不相交。
如果相交，让pA、pB分别从指向链表头部，根据lenA、lenB判断哪个链表更长，让更长链表的指针先走
|lenA-lenB|步，然后pA、pB同时走，直到pA == pB，则pA或pB即为相交节点。
伪码：

  1. public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
  2.     if (headA == null || headB == null) 
  3.         return null;
  5.     int lenA = 0, lenB = 0;
  6.     ListNode pA = headA, pB = headB;
  8.     // pA,pB分别遍历至尾结点并计数
  9.     for(; pA.next != null; pA = pA.next, lenA ++);
  10.     for(; pB.next != null; pB = pB.next, lenB ++);
  11.     if (pA != pB) 
  12.         return null;
  14.     // pA指向更长链表的头结点，pB指向较短的
  15.     pA = headA;
  16.     pB = headB;
  17.     if (lenA < lenB) {
  18.         pA = headB;
  19.         pB = headA;
  20.     }
  22.     // 较长先走
  23.     for(int i = 0; i < Math.Abs(lenA - lenB); nodeA = nodeA.next, i++);
  24.     // 再同时走
  25.     for(;nodeA != nodeB;nodeA = nodeA.next, nodeB = nodeB.next);
  26.     return nodeA;
  27. }

方法二

同样两个指针pA、pB同时走，如果pA == null，则让pA = headB（即指向B链表头结点），否则pA = pA.next，如果pB == null ，则让pB = headA（即指向A链表头结点）, 否则pB = pB.next。循环终止条件是pA != pB。

  • 如果两条链表不相交，则两个指针pA、pB同时走了 lenA + lenB 步后分别到达了B链、A链的末尾，都为null，循环结束。

image.png

  • 如果两条链表相交，则两个指针同时走了相同步数 x + y + z 后，同时到达相交节点。

image.png
伪码：

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;
}

总结

方法二代码更简洁，方法一更容易想到和理解

例题

leetcode 160. 相交链表