【算法100天 | 20】有环/无环链表的相交问题（Java实现）

若两个链表相交，请返回相交的第一个节点。

给定两个有可能有环也有可能无环的单链表，头节点head1和head2。

实现一个函数，如果两个链表相交，请返回相交的第一个节点（从这个节点开始，后续结构都一样）。如果不相交，返回null。

复杂度要求：

• 如果两个链表长度之和为N，要求：时间复杂度为O(n)，额外空间复杂度为O(1)。

该题目可以理解为LeetCode 160. 相交链表的升级版，因为LeetCode160题中的链表是无环的，所以就简单了很多！！

思路

既然两个链表head1、head2可能有环，也可能无环，我们先判断这两个链表到底是不是有环链表，这是会有三种情况：

• 一个链表有环、一个链表无环。
• 两个链表都无环。
• 两个链表都有环。

第一种情况（一个链表有环、一个链表无环）最简单，两个链表肯定不相交。

第二种情况（两个链表都无环），判断两个链表长度的差值x，长的链表先往后走x步，然后再让两个链表一起往后走，如果两个链表当前节点不相等就一直到往后走，直到走到链表尾部。

第三种情况（两个链表都有环），最复杂，其中又细分三种情况。

1> 第一种情况：两个链表不相交，各玩个的。
2> 第二种情况：两个链表相交了，相交节点在入环节点 及其之前（即：入环节点是同一个）。则以入环节点为尾，计算前面链表的长度；然后再和无环链表相交一样处理。

• 入环节点的查找方式：

  • 快慢指针法，快慢指针同时从head出发，判断出链表是有环链表。
  • slow从相交节点开始继续走、fast节点放到head继续往后走，都每次走一步，则它俩相遇的节点是链表环的第一个节点。
    3> 第三种情况：两个链表相交了，但入环节点不是同一个；

• 假设head1的入环节点为loopNode1，head2的入环节点为loopNode2。
• 从loopNode1开始在环里转，如果能遇到loopNode2，返回loopNode1；
• 如果都转了一圈了，也找不到loopNode2，那就是两个链表不相交。
• 注意：可以返回loopNode1，也可以返回loopNode2。

代码

/**
 * 方法二：不使用容器
 * 时间复杂度为O(n)，额外空间复杂度为O(1)。
 */
public static ListNode getIntersectNode(ListNode head1, ListNode head2) {
    if (head1 == null || head2 == null) {
        return null;
    }
    // head1's first into loop node
    ListNode loopNode1 = getLoopNode(head1);
    ListNode loopNode2 = getLoopNode(head2);

    // both no_loop
    if (loopNode1 == null && loopNode2 == null) {
        return noLoop(head1, head2);
    }

    // both loop
    if (loopNode1 != null && loopNode2 != null) {
        /**
         * 几种情况：
         *     1) 两个链表不相交，各自玩自己的
         *     2) 两个链表相交了，相交节点在入环节点 及其之前（即：入环节点是同一个）。
         *           以入环节点为尾，计算前面链表的长度，然后和无环链表相交一样处理。
         *     3）两个链表相交了，入环节点不是同一个
         *         从loopNode1开始在环里转，如果能遇到loopNode2，返回loopNode1；如果都转了一圈了，也找不到loopNode2，那就是两个链表不相交
         *         可以返回loopNode1，也可以返回loopNode2
         */
        return bothLoop(head1, loopNode1, head2, loopNode2);
    }

    // one loop another no_loop
    return null;
}

private static ListNode noLoop(ListNode head1, ListNode head2) {

    // n -> head1 and head2 's count of difference nodes
    int n = 0;
    ListNode curr1 = head1;
    ListNode curr2 = head2;
    while (curr1.next != null) {
        n++;
        curr1 = curr1.next;
    }
    while (curr2.next != null) {
        n--;
        curr2 = curr2.next;
    }
    // tail node is different ，must not intersect
    if (curr1 != curr2) {
        return null;
    }

    // head1 and head2 who more long who curr1, else curr2
    curr1 = n > 0 ? head1 : head2;
    curr2 = curr1 == head1 ? head2 : head1;
    n = Math.abs(n);
    while (n > 0) {
        n--;
        curr1 = curr1.next;
    }
    while (curr1 != curr2) {
        curr1 = curr1.next;
        curr2 = curr2.next;
    }
    return curr1;
}

/**
 * both head is loop
 *
 * @param loop1 head1's first into loop node
 * @param loop2 head2's first into loop node
 */
private static ListNode bothLoop(ListNode head1, ListNode loop1, ListNode head2, ListNode loop2) {
    if (loop1 == loop2) {
        int n = 0;
        ListNode curr1 = head1;
        ListNode curr2 = head2;
        while (curr1 != loop1) {
            n++;
            curr1 = curr1.next;
        }
        while (curr2 != loop2) {
            n--;
            curr2 = curr2.next;
        }

        // head1 and head2 who more long who curr1, else curr2
        curr1 = n > 0 ? head1 : head2;
        curr2 = curr1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n > 0) {
            n--;
            curr1 = curr1.next;
        }
        while (curr1 != curr2) {
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        return curr1;
    } else {
        ListNode curr1 = loop1.next;
        while (curr1 != loop1) {
            if (curr1 == loop2) {
                return loop1;
            }
            curr1 = curr1.next;
        }
    }
    return null;
}


/**
 * 找到链表的第一个入环节点，如果无环返回null。
 */
public static ListNode getLoopNode(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    // slow and fast pointer go one step
    ListNode slow = head.next;
    ListNode fast = head.next.next;
    while (slow != fast) {
        // no_loop
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    /**
     * find first into loop node
     *     1) slow go from intersect node, step equal 1
     *     2) fast become head, and go, stop equal 1, until fast = slow.
     */
    fast = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145