带环链表相交问题_有环单链表相交的交点

  带环链表交点完整代码在最后。

1不带环链表相交

1.1问题描述

LeetCode-相交链表：
  编写一个程序，找到两个单链表相交的起始节点。

  如下面的两个链表：

  在节点 c1 开始相交，若两链表不相交，则返回null。

  如上图所示（其中abc表示节点的个数），使用两个指针x和y分别指向链表1和链表2的起始位置开始向后遍历：

  对于有交点的链表：

• x指针从链表1开始向后走，当走到链表1的末尾时，其走过了a+c个节点，此时将x指针指向链表2的头部。
• y指针从链表2开始向后走，当走到链表2的末尾时，走过了b+c个节点，此时将y指针指向链表1的头部。
• 可以看出，x从链表2向后走b，y从链表1向后走a，此时指针x和y指向了两个链表的交点处，而此时两个指针也走过了同样长的路x：a+c+b；y：b+c+a。

1.2代码实现

所以代码可以实现如下：

ListNode x = headA;
ListNode y = headB;
while(x!=y){
    x = (x == null ? headB : x.next);
    y = (y == null ? headA : y.next);
}
1
2
3
4
5
6

  对于无交点的链表同理，如上图所示，指针x走过a+c+b后指向链表2的末尾null；指针y走过c+b+a后指向链表1的末尾null。即此时指针指针x和y指向了两个链表的“交点”null处。

  可以看出无论两个链表是否有交点，两个指针最终都会指向同一位置，所以最终返回其中一个指针的指向即可。由于上述分析中a,b,c取值的任意性，其也包含了等于0的情况，所以对于链表为空的边界条件无需另外处理。最终的代码如下：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode x = headA;
    ListNode y = headB;
    while(x != y){
        x = (x == null ? headB : x.next);
        y = (y == null ? headA : y.next);
    }
    return x;//也可以return y;
}
1
2
3
4
5
6
7
8
9

2带环链表相交

2.1问题描述

  对于上述不带环问题做额外拓展：其中带环的情况包括下面4种，如果有交点，则返回相交的起始节点，否则返回null。

  图中箭头表示链表指针的方向。

  思路：首先需要判断链表是否带环。假设这里已经判断出来了（判断带环代码后边给出）。

  对于情况1：一个链表带环另一个链表不带环，则一定没有交点。因为不带环链表与带环链表有交点，那么不带环的链表会拥有带环链表的环，此时该不带环链表有环，就变成了情况3.

  对于情况3：可以看出，两个链表交于环外，其环外情况和上一节中的不带环链表相交的问题类似，只不过上一节中的不带环链表的末尾节点是null，而情况三对应的末尾是环的入口节点（两个环的入口节点一样），如下图所示：

  对于情况4：
  可以看出，环入口节点即为交点，因此可以从任意一个链表的环入口对环遍历一周，遍历过程中发现了另一个环入口的点，说明相交。而不同的遍历方式会导致起始相交节点不同：若从链表1的环入口节点出发遍历，则链表2的环入口节点是他们的起始交点，同理，若从链表2的环入口节点开始遍历，则链表1的环入口节点是他们的起始交点。因此对于情况4随机返回链表1或链表2的环入口。

  如果对于两个带环链表，上述情况都不满足，说明这两个链表不相交，即情况2.

2.2各代码实现

2.2.1链表是否带环判断

LeetCode-环形链表使用快慢指针。

分析：
  如果链表不带环，则有终点null。相当于两个人跑100米，跑的快的那个人先到达终点（遇到null），如果链表带环，相当于两个人从宿舍出发去操场的400米跑道锻炼，跑的快的先进入操场（环），跑的满的后进入操场，进入操场后，两个人在跑道上一直转圈跑，跑的快的会在某一时刻与跑的慢的相遇（指向同一位置）。

  代码实现如下：

public boolean hasCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    //刚开始起点一样，所以要先do一下跑起来
    do{
        if(fast == null || fast.next == null){
            return false;
        }
        fast = fast.next.next;
        slow = slow.next;
    }while(fast!=slow);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2.2带环链表入口节点

LeetCode–环形链表II
  思路如下：

  代码实现：

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    do{
        if(fast == null || fast.next == null){
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
    }while(fast != slow);
    
    ListNode cur = head;
    while(cur != slow){
        cur = cur.next;
        slow = slow.next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.2.3初始相交节点代码

  1.分别寻找链表1和链表2的入环节点：

//位于主算法的代码
ListNode entranceA = detectCycle(headA);
ListNode entranceB = detectCycle(headB);
1
2
3

  2.对于无环链表，其入环节点为null。

  如果两个链表都无环，则：

entranceA == entranceB;//都为null
1

  而对于上边分析的情况三，两个环入口节点相等：

entranceA == entranceB;
1

  因此，我们可以统一处理这两种情况的交点，只需对文章最开头的相关方法进行重载即可：(即为其多传入一个环入口节点参数，将原方法中的null替换为该节点)

public ListNode getIntersectionNode(ListNode headA, ListNode headB, ListNode entranceA) {
    ListNode x = headA;
    ListNode y = headB;
    while(x != y){
        x = (x == entranceA ? headB : x.next);
        y = (y == entranceA ? headA : y.next);
    }
    return x;//也可以return y;
}
1
2
3
4
5
6
7
8
9

  找交点：

//位于主算法的代码
if (entranceA == entranceB) {
    return getIntersectionNode(headA, headB, entranceA);
}
1
2
3
4

  3.情况1：一个带环一个不带环（即entranceA或entranceB为空）：

//位于主算法的代码
if (entranceA == null || entranceB == null) {
    //两链表有交点，一个带环则另一个必带环。否则一定无交点
    return null;
}
1
2
3
4
5

  4.情况4的代码

//位于主算法的代码
ListNode tmp = entranceA;//也可以从entranceB开始找
do {
    if (tmp == entranceB) {
        //相交在环上，A的环入口节点或B的环入口节点都是相交起始点（看对谁来说）
        //所以随机返回一个
        return new Random().nextInt(2) == 0 ? entranceA : entranceB;
    }
    tmp = tmp.next;
} while (tmp != entranceA);
1
2
3
4
5
6
7
8
9
10

  5.其他情况：没有交点

return null;
1

3代码汇总

  带环链表相交的代码汇总：

/**
 * 找到两个链表相交的起始节点
 *
 * @param headA 链表A
 * @param headB 链表B
 * @return 有交点返回相交的起始节点，没有返回null
 */
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode entranceA = circleEntrancePoint(headA);
    ListNode entranceB = circleEntrancePoint(headB);
	//(1)无环链表和环入口节点相等的链表
    if (entranceA == entranceB) {
        return getIntersectionNode(headA, headB, entranceA);
    }
    //(2)一个带环一个不带环
    if (entranceA == null || entranceB == null) {
        //两链表有交点，一个带环则另一个必带环。否则一定无交点
        return null;
    }
	//(3)情况4的代码
    ListNode tmp = entranceA;//也可以从entranceB开始找
    do {
        if (tmp == entranceB) {
            //相交在环上，A的环入口节点或B的环入口节点都是相交起始点（看对谁来说）
            //所以随机返回一个
            return new Random().nextInt(2) == 0 ? entranceA : entranceB;
        }
        tmp = tmp.next;
    } while (tmp != entranceA);
    //没有交点
    return null;
}

/**
 * 求带环链表的入口节点
 *
 * @param head 带环链表头结点
 * @return 返回入口节点
 */
private static ListNode circleEntrancePoint(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    do {
        if (fast == null || fast.next == null) {
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);

    ListNode cur = head;
    while (cur != slow) {
        cur = cur.next;
        slow = slow.next;
    }
    return slow;
}

//重载不带环链表的方法
public static ListNode getIntersectionNode(ListNode headA, ListNode headB, ListNode intersect) {
    ListNode a = headA;
    ListNode b = headB;
    while (a != b) {
        a = (a == intersect ? headB : a.next);
        b = (b == intersect ? headA : b.next);
    }
    return a;
}
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