单链表相交的一系列问题

发表于 | 分类于

单链表相交的一系列问题

在给定的单链表中，单链表可能有环，可能无环。判断链表是否相交

​ 要求：如果链表1的长度为N，链表2的长度为M，时间复杂度达到了O(M+N),额外空间复杂度为O(1)。

这道题需要分析的情况很多，额外空间复杂度O(1)的限制。

本题可以拆分为三个子问题，每个问题都可以作为一道独立的算法题，具体如下：

  • 问题一：如何判断一个链表是否有环，如果有，返回第一个进入环的节点，没有则返回null。

  • 问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

  • 问题三：如何判断两个有环链表是否相交，相交返回第一个节点，不相交返回null。

问题一：判断一个链表是否有环

如果链表不存在环，那么遍历链表一定可以遇到链表的终点，如果有环就会一直遍历下去，如何找到第一个入环节点

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
public Node getLoopNode(Node head){
    
    if(head == null || head.next == null || head.next.next == null){
        return null;
    } 
    /*n1为慢指针，n2为快指针*/
    Node n1 = head.next;
    Node n2 = head.next.next;
    /*当快慢指针没有相遇的时候*/
    while(n1 != n2)
    {
        /*如果快慢指针到达终点，说明链表无环*/
        if(n2.next==null || n2.next.next== null)
        { return null;}
        
        n2 = n2.next.next;
        n1 = n1.next;
    }
    
    /*若快慢指针相遇，说明链表有环*/
    /*此时将快指针折返到头部*/
    n2 = head;
    /*此时将快慢指针都设置为每次走一步，相遇时就是环的起点（证明略）*/
    while(n1 != n2)
    {
        n1 = n1.next;
        n2 = n2.next;
    }
    return n1;
}
问题二：判断两个无环链表是否相交

相交返回第一个节点，否则返回null。

如果两个无环链表相交，那么从相交节点到两个链表中止的这段链表是两个链表共享的。

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
public Node noLoop(Node head1, Node head2)
{
    if(head1 == null || head2 == null)
    {return null;}
    /**/
    Node cur1 = head1;
    Node cur2 = head2;
    int n = 0;
    /*遍历Node1和Node2，记录Node1和Node2的尾节点*/
    
    while(cur1.next != null){
        n++;
        cur1 = cur1.next;
    }
    while(cur2.next != null){
        n--;
        cur2 = cur2.next;
    }
    /*如果链表1和链表2的尾节点不同，说明链表1和链表2不相交*/
    if(cur1 != cur2){
        return null;
    }
    /*若链表1比较长，链表1先走len1-len2步，如果是链表2，则走len2-len1步*/
    /*随后两个链表一起走，第一个相交的节点就是交点*/
    cur1 = n > 0 ? head1 : head2;
    cur2 = cur1 == head1?head2:head1;
    n=Math.abs(n);
    /*长链表先走|len1-len2|步*/
    while(n != 0){
        n--;
        cur1 = cur1.next;
    }
    while(cur1 != cur2)
    {
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return cur1;
}
问题三：如何判断两个有环链表是否相交

相交返回第一个相交节点，不相交返回null。

考虑问题三的时候，我们已经得到了两个链表各自的第一个入环节点，假设链表的第一个入环节点记为loop1，链表2的第一个入环节点记为loop2。

1如果loop1 == loop2

那么两个链表的拓扑结构如下

在这种情况下我们只需要考虑链表1和链表2从头开始的这一段，在哪里第一次相交即可。不过这里把loop1(loop2)作为链表的终点。

2如果loop1 != loop2

两个链表不相交的拓扑结构和相交的拓扑结构如下所示。

如何分辨是哪一种拓扑结构？

让链表1从loop1出发，因为loop1和之后 的节点都在环上，如果loop1在回到本身之前没有遇到loop2，那么链表的拓扑结构就是第一种，返回null。

否则的话，说明链表1和链表2相交，那么此时返回loop1或者loop2都可以。

具体实现如下。

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
public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2)
{
    Node cur1 = null;
    Node cur2 = null;
    /*如果loop1 == loop2，这种情况下我们只需要考虑链表头节点到loop的这一段*/
    /*这段代码与判断两个无环链表相交类似*/
    if(loop1 == loop2){
        cur1 = head1;
        cur2 = head2;
        int n = 0;
        while(cur1 != loop1){
            n++;
            cur1 = cur1.next;
        }
        while(cur2 != loop2)
        {
            n--;
            cur2 = cur2.next;
        }
        cur1 = n> 0?head1:head2;
        cur2 = cur1 == head1?head2:head1;
        n = Math.abs(n);
        while(n!=0)
        {
            cur1 = cur1.next;
        }
        while(cur1 != cur2)
        {
            cur1 =cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }else
    {
        /*如果loop1 != loop2*/
        cur1 = loop.next;
        while(cur1 != loop1)
        {
            if(cur1 == loop2){
                return loop1;
            }
            cur1 = cur1.next;
        }
        return null;
    }
}
题目的主方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Node{
    public int value;
    public Node next;
    public Node(int data){
        this.value = data;
    }
}

public Node getIntersectNode(Node head1, Node head2)
{
    if(head1 == null || head2 == null){
        return null;
    }
    Node loop1 = getLoopNode(head1);
    Node loop2 = getLoopNode(head2);
    /*如果两个链表都无环*/
    if(loop1 == null && loop2 == null){
        return noLoop(head1, head2);
    }
    if(loop1 != null && loop2 != null){
        return bothLoop(head1, loop1, head2, loop2);
    }
    return null;
}