1 题目描述

160. 相交链表要求给定两个单链表的头节点 headA 和 headB，任务是找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

2 解题思路

为了解决这个问题，我们可以采用以下策略：

1. 计算两个链表的长度：首先分别遍历两个链表以获取它们的长度。
2. 使较长链表的头指针与较短链表的头指针对齐：如果一个链表比另一个长，我们需要让较长链表的头指针先向前移动长度差步，使得两个链表的指针处于同一位置。
3. 同步移动两个指针直至相交：当两个链表的指针位于同一位置时，我们同步移动这两个指针。一旦两个指针相遇，即找到了相交节点。

3 Java 代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        
        // 求链表A的长度
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        
        // 求链表B的长度
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }
        
        curA = headA;
        curB = headB;
        
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            // 交换 lenA 和 lenB
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            // 交换 curA 和 curB
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        
        // 求长度差
        int gap = lenA - lenB;
        
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        
        return null;
    }
}

• 时间复杂度: O(L1 + L2)，其中 L1 和 L2 分别是链表 A 和链表 B 的长度。我们需要遍历每个链表一次来计算长度，然后再遍历一次以找到相交节点。
• 空间复杂度: O(1)，因为我们只使用了几个指针变量。

4 注意事项

• 计算长度：先计算两个链表的长度，以便知道哪个链表更长。
• 对齐起点：让较长的链表先走长度差步，使得两个链表的末尾对齐。
• 同步遍历：然后同步遍历两个链表，直到找到相同的节点或到达链表末尾。
• 返回结果：如果找到相交节点，返回该节点；否则返回 null。