程序员面试金典（第 6 版）

面试题 02.07. 链表相交

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

思路：

• 交点不是数值相等，而是指针相等
• 如果两个单链表有交点，则交点及后半部分是重合的
• 先求出两个链表的长度，并求出两个链表长度的差值
• 通过差值，让两个指针移动到两个链表末尾对齐的位置，如下所示。并依次比较
• 

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        // 两个链表的长度
        int lengthA = 0;
        int lengthB = 0;
        // 求出两个链表的长度
        while (curA != null) {
            lengthA++;
            curA = curA.next;
        }
        while (curB != null) {
            lengthB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让 headA、curA 为最长的那个链表
        if (lengthB > lengthA) {
            int tempLength = lengthA;
            lengthA = lengthB;
            lengthB = tempLength;
            ListNode tempNode = curA;
            curA = curB;
            curB = tempNode;
        }
        int gap = lengthA - lengthB;
        // 让 curA 和 curB 在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历 curA 和 curB，遇到相同节点则返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            } else {
                curA = curA.next;
                curB = curB.next;
            }
        }
        return null;
    }
}