160.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

Solution：双指针

两个指针分别从两个链表起始处出发，同时增加，如果到了尽头，就从另一个链表起始处开始，如果两个链表相交，则指针必会在相交处相等，如果不相交，则必会同时到尽头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = new ListNode(-1); // 创建一个新的节点l1，但实际上没有使用新节点的功能，仅用于参考。
        l1 = headA; // 将l1指针指向链表A的头部。
        ListNode l2 = new ListNode(-1); // 创建一个新的节点l2，同样，实际上没有使用新节点的功能。
        l2 = headB; // 将l2指针指向链表B的头部。
        int flag1 = 0; // 用于标记l1是否已经从headA跳到headB。
        int flag2 = 0; // 用于标记l2是否已经从headB跳到headA。

        // 遍历两个链表直到两个指针相遇或遍历结束
        while (l1 != null && l2 != null) {
            if (l1 == l2) { // 如果在某个点l1和l2相遇，返回该相交点。
                return l2;
            }
            l1 = l1.next; // 移动l1到下一个节点。
            if (l1 == null && flag1 == 0) { // 如果l1到达链表A的末尾并且还没有跳转到链表B
                flag1 = 1; // 标记已经跳转
                l1 = headB; // 将l1跳转到链表B的头部
            }
            l2 = l2.next; // 移动l2到下一个节点。
            if (l2 == null && flag2 == 0) { // 如果l2到达链表B的末尾并且还没有跳转到链表A
                flag2 = 1; // 标记已经跳转
                l2 = headA; // 将l2跳转到链表A的头部
            }
        }
        return null; // 如果两个链表不相交，返回null。
    }
}