两个单链表相交的一系列问题

发表于 阅读次数：

问题

在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点head1
和head2，这两个链表可能相交，也可能不相交，请实现一个函数，如果两个
链表相交，请返回相交的第一个节点；如果不相交，返回null即可。要求:
如果链表1长度为N，链表2的长度为M,时间复杂度请达到O(N+M),额外空间
复杂度请达到O(1)。

本题可以分化成3个小问题

  1. 判断单链表是否有环

  2. 求两个无环单链表第一个相交的节点

  3. 求两个有环单链表第一个相交的节点

环和相交的图例

我们可以先把每一个小问题都解决了再回头看整道题

思路

问题1：判断单链表是否有环，附加条件：如有环，返回第一个入环的节点

判断单链表是否有环有两种思路：

  • 一是使用HashSet，遍历链表判断节点是否存在，若不存在则放入set中，利用set的数据具有唯一性的特点，若节点已存在于set中，则表明是有环的。第一个入环的节点就是第一个重复的节点。

  • 二是快慢指针法，设置快慢指针，快慢指针重合在一起则表明有环。快慢指针重合时把快指针移动到链表的头部，然后两指针都按一次一步移动，再次重合的位置则是入环的节点。(不要问我为什么，我也很迷)

问题2：求两个无环单链表第一个相交的节点

若两个链表都没环，有两种方式获取第一个相交的节点

  • 一是使用Map，遍历head1的链表并放入map中，再遍历head2判断是否存在于map中，存在（第一个）则返回，若无则表明不相交。

  • 二是计算两个链表的长度并保存两者最后的节点地址，若最后节点相等则必定相交，那么如何获取第一个相交节点呢？很简单，把两者的长度相减，让两条链表中较长的走相应的步数，这样大家都站在同一起跑线上了，两条链表同时移动，每次一步，当他们重合的时候即为第一个相交节点。

此为两个链表无环。

注：一个有环一个没环相交，在单链表中是不存在，请读者自行画图。

问题3：求两个有环单链表第一个相交的节点

两个链表有环有一下三种情况，

我们上面已经得出第一个入环节点(下面称loop1/loop2)。

  • 若loop1 == lopp2 则是入环前相交。
  • 若loop1 != loop2 ,且在loop1进行一轮循环内找到与loop2相等的节点，则是入环后相交
  • 剩下的情况则为不相交

判断完情况后就要求出第一个相交的节点

  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
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    //判断链表是否有环，若有环则返回第一个入环的节点  如：1->2->3->4->5->6->7->4  4就是入环的第一个节点
    public static Node getLoopNode(Node head) {

        if(head == null || head.next == null || head.next.next == null) {
            return null;
        }
        //1 2 3 4 5 3
        Node slow = head.next;
        Node fast = head.next.next;
        while(slow != fast) {
            ////无环的话fast迟早有null，直接返回null
            if(fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        //slow和fast撞上了，证明有环，下面开始取第一个入环的节点
        //快指针回头部，两个指针一步一步走，重合即停并返回
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public static Node noLoop(Node head1, Node head2) {
        Node current1 = head1;
        Node current2 = head2;
        int gap = 0;
        while(current1.next != null) {
            current1 = current1.next;
            gap++;
        }
        while(current2.next != null) {
            current2 = current2.next;
            gap--;
        }
        //不相交
        if(current2 != current1) {
            return null;
        }
        //相交
        //把较长的链表放入current1中
        current1 = gap > 0 ? head1 : head2;
        //你1做长，那2就是短咯
        current2 = current1 == head1 ? head2 : head1;
        gap = Math.abs(gap);
        //长的先跑
        while(gap != 0) {
            gap--;
            current1 = current1.next;
        }
        //重合即为第一个相交节点
        while(current1 != current2) {
            current1 = current1.next;
            current2 = current2.next;
        }
        return current1;
    }

    public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
        Node current1;
        Node current2;
        //入环前相交
        if(loop1 == loop2) {
            current1 = head1;
            current2 = head2;
            int gap = 0;
            while(current1 != loop1) {
                gap++;
                current1 = current1.next;
            }
            while(current2 != loop2) {
                gap--;
                current2 = current2.next;
            }
            current1 = gap > 0 ? head1 : head2;
            current2 = current1 == head1 ? head2 : head1;
            gap = Math.abs(gap);
            while(gap != 0) {
                current1 = current1.next;
                gap--;
            }
            while(current1 != current2) {
                current1 = current1.next;
                current2 = current2.next;
            }
            return current1;
        }else {
            //loop1走一轮，看下有没有看到loop2，有就是入环后相交直接返回其中一个入环节点即可，没有就是没相交
            current1 = loop1.next;
            while(current1 != loop1) {
                if(current1 == loop2) return loop1;
                current1 = current1.next;
            }
            return null;
        }
    }

    public static 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,head2,loop1,loop2);
        }
        return null;
    }

    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

        // 1->2->3->4->5->6->7->4...    有环
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...   有环，入环前相交
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);

        // 0->9->8->6->4->5->6..    //入环后相交
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);
    }