Fork me on GitHub

链表相关经典问题

发表于 | 分类于 | | 阅读次数:
字数统计: 3,680 | 阅读时长 ≈ 16

前言

链表实际上是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，且链表的长度不是固定的，链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作。

链表的每个元素称为一个节点，每个节点都可以存储在内存中的不同的位置，为了表示每个元素与后继元素的逻辑关系，以便构成“一个节点链着一个节点”的链式存储结构，除了存储元素本身的信息外，还要存储其直接后继信息。

因此，每个节点都包含两个部分，第一部分称为链表的数据区域，用于存储元素本身的数据信息，可以用data表示，它不局限于一个成员数据，也可是多个成员数据，第二部分是一个结构体指针，称为链表的指针域，用于存储其直接后继的节点信息，可以用next表示，next的值实际上就是下一个节点的地址，当前节点为末节点时，next的值设为空指针。

链表代码可以用下述代码表示。

1
2
3
4
5
6
7
8
private class Node{
    private int data;
    private Node next;

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

正文

我们来看一下关于链表的一些经典问题。

  1. 如何判断一个链表是否有环？如果有环，如何找到环入口节点？
  2. 如何判断两个链表是否相交？

对于上述问题，我们分别来看一下。

是否环链表

对于第一个问题，我们可以采用“快慢指针”的方法来解决。如下图：

upload successful

思路：（结论1）设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点。

（结论2）接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口。

我们来看下这两个结论。

结论1：设置快慢指针fast和slow，fast每次走两步，low每次走一步。假如有环，两者一定在环中相遇。（因为low指针一旦进环，可以看作是fast指针在追slow指针，因为fast指针每次走两步，slow指针每次走一步，所以最后一定能相遇）。

结论2：我们看上面的简化图，链表头a到链表环入口节点b的距离定义为l，环入口b到相遇点p的距离（右边）定义为m，相遇点p到环入口b的距离（左边）定义为n。

当快指针和慢指针相遇时：

快指针路程 = l+(m+n)k+m，k>=1，其中m+n为环的长度，k为环的圈数（k>=1，即最少一圈，不能是0圈，不然快慢指针走的路程一样，矛盾）。

慢指针路程 = l+m。

因为快指针的路程是慢指针的路程的两倍，所以：(l+m)*2 = l+(m+n)k+m，其中k>=1。

化简得到 l =(k-1)(m+n)+n

这个式子的意思是：链表头到环入口的距离=相遇点到环入口的距离+(k-1)圈数环长度。其中k>=1，所以k-1>=0圈。 所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

根据上面内容，可以写出判断是否为环链表的代码及找到环入口节点的代码。

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
/**
    * 链表节点
    */
private static class Node{
    private int data;
    private Node next;

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

/**
    * 是否环链表
    * @param head
    * @return
    */
public static boolean isLoop(Node head){
    Node fast = head;
    Node slow = head;
    while(slow !=null && fast != null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

/**
    * 获取环链表入口节点
    * @param head
    * @return
    */
public static Node getLoopStartNode(Node head){
    //快慢指针
    Node fast = head;
    Node slow = head;
    while(slow !=null && fast != null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
        //相遇退出，此时快慢指针位置为相遇点
        if(slow == fast){
            break;
        }
    }
    //如果没有环，return null
    if (fast==null || fast.next == null || fast.next.next == null) {
        return null;
    }

    slow = head;
    //如果有环，两个指针分别从链表头和相遇点出发，最终必定在环入口相遇
    while (slow!=fast){
        slow = slow.next;
        fast = fast.next;
    }
    return fast;
}

其实获取环链表入口节点返回null，也代表该链表不是环链表。

我们再来看下第二个问题，如何判断两个链表是否相交。

两个链表一般有这三种情况：两个无环链表、两个有环链表、一个有环链表和一个无环链表。

对于上面三种情况，我们分别来看下：

两个无环链表相交问题

两个无环链表A、B如果相交，则在相交点及之后的节点必然相同。如下图：

upload successful

这非常容易理解，当A、B链表相交后，相交节点如果为PNode，则下一个节点 PNode.next 即是A的节点，也是B的节点。

因为从相交点往后两链表都是相同的，我们往前移动一定位置，较短的链表会到链表头。

因此我们以A、B当中较短的链表长度为准，从该位置遍历比较两个链表节点，如果节点相同，则说明A、B相交。

代码如下：

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
/**
    * 判断两个无环链表是否相交
    * @param node1
    * @param node2
    * @return
    */
public static boolean noLoopNodeIsIntersect(Node node1,Node node2){
    if(node1==null||node2==null){
        return false;
    }

    Node temp1 = node1;
    Node temp2 = node2;

    //PS：两个链表相交，相交点及之后的节点会完全一致
    //1.拿到两链表长度
    int size1 = 0;
    int size2 = 0;
    while (temp1!=null){
        size1++;
        temp1 = temp1.next;
    }
    while (temp2!=null){
        size2++;
        temp2 = temp2.next;
    }

    //2.对于较长的链表，遍历到与短链表相同长度
    if(size1 > size2){
        int p1 = size1 -size2;
        while (p1>0){
            node1 = node1.next;
            p1--;
        }
    }else{
        int p2 = size2 -size1;
        while (p2>0){
            node2 = node2.next;
            p2--;
        }
    }

    //3.此时两个链表位置相同，同时向下遍历，如果有相同节点，说明相交
    while (node1!=node2){
        node1 = node1.next;
        node2 = node2.next;
    }
    //找到相交点，返回成功
    if(node1!=null){
        return true;
    }
    //遍历到最后仍没有相交点，返回false
    return false;
}

两个有环链表相交问题

如果两个有环链表相交，则相交部分一定包含整个环。如下图：

upload successful

一般有一个环入口节点和两个环入口节点两种情况。

因此我们可以先求两个环链表的入口节点，见上面代码。

  1. 如果入口节点是同一个的话，把相同的入口节点当作是尾节点，这个问题就退化成两个链表都无环，直接判断是否相交即可。
  2. 如果入口节点不是同一个的话，从第一个入口节点开始next下去，如果遇到第二个入口节点返回true即可；如果回到了本身的入口节点则表示没有相交，直接返回false。

相关代码如下：

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
/**
    * 判断两个环链表是否相交
    * @param head1 环链表1 头
    * @param loop1 环链表1 环入口节点
    * @param head2 环链表2 头
    * @param loop2 环链表2 环入口节点
    * @return
    */
public static boolean bothLoopNodeIsIntersect(Node head1, Node loop1, Node head2, Node loop2){
    Node cur1 = null;
    Node cur2 = null;
    //如果两个链表的环入口节点是同一个
    if (loop1 == loop2) {
        cur1 = head1;
        cur2 = head2;
        int n = 0;
        //判断链表1和链表2谁到入口节点的长度长
        while (cur1 != loop1) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2 != loop2) {
            n--;
            cur2 = cur2.next;
        }
        //长的标记为cur1
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        //遍历长链表直到位置和短链表头位置相等
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        //两个链表长度相等开始遍历，直到相等时退出
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //找到相交点，返回成功，否则返回失败
        if(cur1!=null){
            return true;
        }
        return false;
    } else {
        //环入口不是同一个，开始以环入口1为起点遍历环
        cur1 = loop1.next;
        while (cur1 != loop1) {
            //如果在环上找到了环入口2，说明就是一个环
            if (cur1 == loop2) {
                return true;
            }
            cur1 = cur1.next;
        }
        //没找到环入口2，说明不是一个环，两个环链表也不可能相交
        return false;
    }
}

一个有环链表和一个无环链表相交问题

一个有环链表和一个无环链表是不可能相交的。

我们来简单分析下，如图：

upload successful

我们假设有环链表A和无环链表B相交于环链表A非环部分的A点（虚线a表示），可以看到，对于非环链表B，当遍历到相交点时，还是可以继续next的，最后B也成为了环链表，这与B是非环链表矛盾。

假设它们相交于环链表A的环部分B点（虚线b表示），同理，对于非环链表B，当遍历到相交点时，还是可以继续next的，最后B也成为了环链表，这与B是非环链表矛盾。

这两种情况都是上面所述的两个环链表相交。

因此一个有环链表和一个无环链表是不可能相交的。

相交问题总结

根据上面的代码及分析，判断链表是否相交的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
    * 判断两个链表是否相交
    * @param head1
    * @param head2
    * @return
    */
public static boolean nodeIsIntersect(Node head1,Node head2){
    if(head1==null || head2 == null){
        return false;
    }
    //拿到环入口节点
    Node loop1 = getLoopStartNode(head1);
    Node loop2 = getLoopStartNode(head2);
    //两链表都为无环链表
    if(loop1==null&&loop2==null){
        return noLoopNodeIsIntersect(head1,head2);
    }
    //两链表都为有环链表
    if(loop1!=null && loop2!=null){
        return bothLoopNodeIsIntersect(head1,loop1,head2,loop2);
    }
    //一个有环一个无环直接返回false
    return false;
}

全部代码如下：

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
public class LinkedList {
    /**
     * Node节点
     */
    private static class Node{
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }
    /**
     * 是否环链表
     * @param head
     * @return
     */
    public static boolean isLoop(Node head){
        Node fast = head;
        Node slow = head;
        while(slow !=null && fast != null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }

    /**
     * 获取环链表入口节点
     * @param head
     * @return
     */
    public static Node getLoopStartNode(Node head){
        //快慢指针
        Node fast = head;
        Node slow = head;
        while(slow !=null && fast != null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            //相遇退出，此时快慢指针位置为相遇点
            if(slow == fast){
                break;
            }
        }
        //如果没有环，return null
        if (fast==null || fast.next == null || fast.next.next == null) {
            return null;
        }

        slow = head;
        //如果有环，两个指针分别从链表头和相遇点出发，最终必定在环入口相遇
        while (slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }


    /**
     * 判断两个无环链表是否相交
     * @param node1
     * @param node2
     * @return
     */
    public static boolean noLoopNodeIsIntersect(Node node1,Node node2){
        if(node1==null||node2==null){
           return false;
        }

        Node temp1 = node1;
        Node temp2 = node2;

        //PS：两个链表相交，相交点及之后的节点会完全一致
        //1.拿到两链表长度
        int size1 = 0;
        int size2 = 0;
        while (temp1!=null){
            size1++;
            temp1 = temp1.next;
        }
        while (temp2!=null){
            size2++;
            temp2 = temp2.next;
        }

        //2.对于较长的链表，遍历到与短链表相同长度
        if(size1 > size2){
            int p1 = size1 -size2;
            while (p1>0){
                node1 = node1.next;
                p1--;
            }
        }else{
            int p2 = size2 -size1;
            while (p2>0){
                node2 = node2.next;
                p2--;
            }
        }

        //3.此时两个链表位置相同，同时向下遍历，如果有相同节点，说明相交
        while (node1!=node2){
            node1 = node1.next;
            node2 = node2.next;
        }
        //找到相交点，返回成功
        if(node1!=null){
            return true;
        }
        //遍历到最后仍没有相交点，返回false
        return false;
    }

    /**
     * 判断两个环链表是否相交
     * @param head1 环链表1 头
     * @param loop1 环链表1 环入口节点
     * @param head2 环链表2 头
     * @param loop2 环链表2 环入口节点
     * @return
     */
    public static boolean bothLoopNodeIsIntersect(Node head1, Node loop1, Node head2, Node loop2){
        Node cur1 = null;
        Node cur2 = null;
        //如果两个链表的环入口节点是同一个
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            //判断链表1和链表2谁到入口节点的长度长
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            //长的标记为cur1
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            //遍历长链表直到位置和短链表头位置相等
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            //两个链表长度相等开始遍历，直到相等时退出
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            //找到相交点，返回成功，否则返回失败
            if(cur1!=null){
                return true;
            }
            return false;
        } else {
            //环入口不是同一个，开始以环入口1为起点遍历环
            cur1 = loop1.next;
            while (cur1 != loop1) {
                //如果在环上找到了环入口2，说明就是一个环
                if (cur1 == loop2) {
                    return true;
                }
                cur1 = cur1.next;
            }
            //没找到环入口2，说明不是一个环，两个环链表也不可能相交
            return false;
        }
    }

    /**
     * 判断两个链表是否相交
     * @param head1
     * @param head2
     * @return
     */
    public static boolean nodeIsIntersect(Node head1,Node head2){
        if(head1==null || head2 == null){
            return false;
        }
        //拿到环入口节点
        Node loop1 = getLoopStartNode(head1);
        Node loop2 = getLoopStartNode(head2);
        //两链表都为无环链表
        if(loop1==null&&loop2==null){
            return noLoopNodeIsIntersect(head1,head2);
        }
        //两链表都为有环链表
        if(loop1!=null && loop2!=null){
            return bothLoopNodeIsIntersect(head1,loop1,head2,loop2);
        }
        //一个有环一个无环直接返回false
        return false;
    }
}

总结

我们通过对链表的一些经典问题进行分析，加深了我们对于链表的一些理解。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力！
0%