关于链表的一些操作

发表于 | 分类于 | 热度: ℃
字数统计: 2,091 | 阅读时长 ≈ 10

前言

最近在“极客时间”学习王争老师《数据结构与算法之美》课程，本文用作学习过程中的代码实践记录。主要是针对一条带头单链表进行链表反转、查询中间结点，检查是否有环，删除倒数第几个结点和合并两个有序链表的操作。

代码

话不多说，直接上示例代码：

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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
package com.structure;

/**
 * @author zhangxingrui
 * @create 2019-01-14 13:43
 **/
public class LinkedList3 {

    // 将一个新节点添加到链表尾部
    public static void addNode(Node listNode, Node node){
        //如果链表是一个空链表，则将此节点赋给链表
        if (listNode == null)
            listNode = node;
        if (listNode != null){
            while (listNode.next != null){
                listNode = listNode.next;
            }
            listNode.next = node;
        }
    }
    // 将node2节点插入到node1后面
    public static void addNode(Node listNode, Node node1, Node node2){
        Node currNode;
        while(listNode.next != null){
            currNode = listNode.next;
            if (currNode.data == node1.data){
                //注意这里需要先将插入的节点的next指向链表插入位置后面
                //再将插入位置的next指向插入节点
                node2.next = currNode.next;
                listNode.next.next = node2;
                break;
            }
            listNode = currNode;
        }
    }
    // 删除链表中的某个值(此链表头结点不存入值）
    public static void removeNode(Node listNode, Node node){
        Node currNode;
        while (listNode.next != null) {
            currNode = listNode.next;
            if (currNode.data == node.data){
                listNode.next = currNode.next;
                break;
            }
            listNode = currNode;
        }
    }
    // 从头部到尾部打印出链表的值(跳过链表的头结点)
    public static void showNode(Node listNode){
        listNode = listNode.next;
        while (listNode != null){
            System.out.println(listNode.data);
            listNode = listNode.next;
        }
    }
    // 获取链表的长度
    public static int getLenOfLNode(Node listNode){
        int len = 0;
        listNode = listNode.next;
        while (listNode != null){
            len++;
            listNode = listNode.next;
        }
        return len;
    }

    // 单链表反转
    public static void reverse(Node list) {
        Node previousNode = null;
        Node currentNode = list.next;
        while (currentNode != null) {
            Node nextNode = currentNode.next;
            if (nextNode == null) {
                list.next = currentNode;
            }
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
    }

    // 判断链表是否有环（通过快慢指针的方式）
    public static boolean checkCircle(Node list) {
        if (list == null || list.next == null)
            return false;

        Node fast = list.next;
        Node slow = list;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (slow == fast) return true;
        }

        return false;
    }

    // 找出中间节点（用于节点数是奇数的情况）
    public static Node findMiddleNode(Node list) {
        if (list == null)
            return null;

        if(getLenOfLNode(list) % 2 == 0)
            return null;

        Node slow,fast;
        slow = fast = list;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 删除倒数第K个结点
    public static void deleteLastKth(Node list, int k) {
        Node fast = list;
        int i = 1;
        while (fast != null && i < k){
            fast = fast.next;
            ++i;
        }

        if(fast == null)
            return;

        Node slow = list;
        Node previousNode = null;
        while (fast.next != null){
            fast = fast.next;
            previousNode = slow;
            slow = slow.next;
        }

        if(previousNode != null){
            previousNode.next = previousNode.next.next;
        }
    }

    // 合并有序链表
    public static Node mergeSortedLists(Node la, Node lb) {
        if (la == null) return lb;
        if (lb == null) return la;

        Node o = la;
        Node p = la.next;
        Node q = lb.next;
        Node head;
        if (p.data < q.data) {
            head = p;
            p = p.next;
        } else {
            head = q;
            q = q.next;
        }
        Node r = head;

        while (p != null && q != null) {
            if (p.data < q.data) {
                r.next = p;
                p = p.next;
            } else {
                r.next = q;
                q = q.next;
            }
            r = r.next;
        }

        if (p != null) {
            r.next = p;
        } else {
            r.next = q;
        }

        o.next = head;
        return o;
    }

    public static void main(String[] args) {
        // 创建一个头结点
        Node list = new Node(0);

        // 创建三个节点，为后面测试使用
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        System.out.println("初始链表，添加1,2,3,4,5节点");
        addNode(list, node1);
        addNode(list, node2);
        addNode(list, node3);
        addNode(list, node4);
        addNode(list, node5);
        showNode(list);

        System.out.println("移除节点3");
        removeNode(list, node3);
        showNode(list);

        System.out.println("在节点2后添加节点3");
        addNode(list, node2, node3);
        showNode(list);

        System.out.println("反转链表");
        reverse(list);
        showNode(list);

        System.out.println("链表是否有环：" + checkCircle(list));

        System.out.println("找出链表的中间节点：" + findMiddleNode(list).data);

        System.out.println("删除倒数第二个节点");
        deleteLastKth(list,1);
        showNode(list);

        System.out.println("合并a链表和b链表");

        Node a = new Node(0);
        addNode(a, new Node(1));
        addNode(a, new Node(3));
        addNode(a, new Node(5));

        Node b = new Node(0);
        addNode(b, new Node(2));
        addNode(b, new Node(4));
        addNode(b, new Node(6));

        Node mergedList = mergeSortedLists(a, b);
        showNode(mergedList);
    }

}

代码整体来讲，多看几遍就懂了，其中比较难理解可能就是检测链表是否有环、找出中间结点和删除倒数第几个结点的操作，这三个方法都用到了快慢指针来做。

检测链表是否有环

首先介绍链表上有环是什么样的情况，请看下图：

我们可以看到链表在B处就进入了一个环，那么我们怎么判断一个链表中是否有环呢？

我们可以设置slow和fast两个指针都指向链表的头部，然后呢slow每次走一步，fast每次走两步，如果fast能到链表尾部那当然就没有环，而如果fast不能到链表尾部，那么它就会在环上一只跑，最终fast会与后来的slow在环上相遇，此时fast == slow，则证明有环。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 检测链表中是否有环
    public static boolean checkCircle(Node list){
        Node slow = list;
        Node fast = list.next;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
                return true;
        }
        return false;
    }

另外一个问题，我们怎么知道这个环的入口结点是哪个呢？

如上图所示，假设链表头A到入口点B的长度为x，C点为slow和fast相遇的地方，环的长度为L，slow走过的距离为S并且当前slow已经在环上走了m圈，fast要与slow相遇它一定比slow多走了n圈，并且fast走的距离是slow的两倍2S。B到C的长度为z，C到B的长度为y，那么我们可以推导出如下公式：

X + Z + mL = S

X + Z + mL + nL = 2S

Z + Y = L

那么

X + Z + mL + nL = 2(X + Z + mL) => nL = X + Z + mL =>

nL = X + (L - Y) + mL => X = (n - m - 1)L + Y

最终得到X = (n - m - 1)L + Y

所以如果我们设置两个指针分别指向链表头A点和C点，两个指针每次走一步，最终会经过(n - m - 1)圈后会相遇，第一次相遇的地方就是环的入口点。

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
// 找出环的入口
    public static Node findEntranceAtLoopList(Node list){
        boolean isLoop = false;

        Node slow,fast;

        slow = fast = list;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                isLoop = true;
                break;
            }
        }

        if(!isLoop)
            return null;

        slow = list;
        while (fast != null && fast.next != null){
            if(slow == fast)
                return slow;

            slow = slow.next;
            fast = fast.next;
        }

        return null;
    }

找出中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 找出中间的结点
    public static Node findMiddleNode(Node list) {
        if (list == null) return null;

        Node fast = list;
        Node slow = list;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

这个就比较简单了，就是利用快慢节点分别从链表头，fast每次走两步，slow每次走一步，那么当fast走到链表尾的时候，slow刚好走到中间的位置上，此时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
// 删除倒数第K个结点
    public static void deleteLastKth(Node list, int k) {
        Node fast = list;
        int i = 1;
        while (fast != null && i < k){
            fast = fast.next;
            ++i;
        }

        if(fast == null)
            return;

        Node slow = list;
        Node previousNode = null;
        while (fast.next != null){
            fast = fast.next;
            previousNode = slow;
            slow = slow.next;
        }

        if(previousNode != null){
            previousNode.next = previousNode.next.next;
        }
    }

这个也比较好理解，就是比如我们要删除倒数第二个点，链表长度为L，那么我们让fast先走两步，然后再让fast和slow一起每次走一步，假设fast总共走了n步到了链表尾，此时slow走了n - 2步，就处在倒数第二个位置上。

参考文章

判断链表是否有环及环入口点的求法

zhangxingrui wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！