LeetCode算法练习top100：（4）链表

package top100.top链表;

import top100.ListNode;
import top100.Node;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;

public class TOP {
    //160. 相交链表
    //hashmap方法太low了
    //判断链表是否相交
    //双指针遍历两个相交链表,如果有相遇点，路径节点数一定相同
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode cur1 = headA, cur2 = headB;
        while (cur1 != cur2) { //如果相交，则一定会有cur1 = cur2，如果不相交，cur1 = cur2 = null
            cur1 = cur1 == null ? headB : cur1.next;
            cur2 = cur2 == null ? headA : cur2.next;
        }
        return cur1;
    }

    //206. 反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //234. 回文链表
    //方法很多，反转链表，或者取出数据再判断
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        for (int i = 0; i < list.size() / 2; i++) {
            int a = list.get(i);
            int b = list.get(list.size() - 1 - i);
            if (a != b) {
                return false;
            }
        }
        return true;
    }
    //反转链表的前一半再同时便利两部分
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode pre = null;
        ListNode slow = head, fast = head;
        //遍历的时候同时反转，很妙
        while(fast != null && fast.next != null){
            // 快指针每次前进两步
            fast = fast.next.next;
            // 每次循环将局部链表反转
            ListNode tmp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = tmp;
        }
        // 1.偶数链表循环结束后，fast == null，
        // pre指向前半部分第一个回文数，slow指向后半部分第一个回文数
        // 2. 奇数链表循环结束后，fast !=null, fast.next == null
        // pre指向前半部分第一个回文数，slow指向后半部分第一个链表。
        // 要将slow向前推进一步
        if(fast != null) slow = slow.next;
        // 此时pre指向前半部分第一个回文数，slow指向后半部分第一个回文数
        while (pre != null || slow != null){
            if(pre.val != slow.val) return false;
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }

    //141. 环形链表
    //链表是否有环：快慢指针，如果有环，肯定会相遇
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    //142. 环形链表 II
    //链表的环：hashmap 或者 双指针
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { //遇到环，快指针重新走
                fast = head;
                while (fast != slow) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    //21. 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode temp = new ListNode(-1);
        ListNode cur = temp;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null) {
            cur.next = list2;
        }
        return temp.next;
    }


    //2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;

        ListNode fake = new ListNode(-1);
        ListNode pre = fake;

        while(l1 != null || l2 != null || carry != 0) {
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;

            ListNode cur = new ListNode((num1 + num2 + carry) % 10);
            pre.next = cur;
            pre = cur;

            carry = (num1 + num2 + carry) / 10;

            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }

        pre.next = null;
        return fake.next;
    }

    //19. 删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //双指针
        ListNode slow = head;
        ListNode fast = head;
        //fast先移动n个，再同时移动fast和slow,使fast在最后一个结点，则slow就是倒数第n个
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        ListNode pre = dummy;
        while (fast != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        pre.next = slow.next;
        return dummy.next;
    }

    //24. 两两交换链表中的节点
    //用了k个一组反转链表的方法
    public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;

        ListNode dummy = head.next;
        ListNode next = dummy.next;
        //翻转
        dummy.next = head;
        head.next = swapPairs(next);
        return dummy;
    }

    //25. K 个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        //计算结点是否有k个
        ListNode cur = head;
        for (int i = 0; i < k; i++) {
            if (cur == null) {
                return head;
            }
            cur = cur.next;
        }
        //翻转k个节点
        ListNode pre = null;
        cur = head;
        int count = 1;
        while (count <= k) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            count++;
        }
        //拼接
        head.next = reverseKGroup(cur, k);
        return pre;
    }

    //138. 随机链表的复制
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        //HashMap记录两个链表的对应情况
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    //148. 排序链表
    //链表的归并排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        //链表分割为两部分：快慢双指针
        //如果链表是偶数， 则需要找到中间节点的第一个
        //如果是找到链表中间节点的第二个，则可以去掉fast.next.next条件
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode temp = slow.next;//slow就是中间节点的第一个
        slow.next = null; //断开链表
        //递归排序两个链表
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        //合并排序后的链表
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        //剩余部分添加到后面
        cur.next = left != null ? left : right;
        return dummy.next;
    }

    //23. 合并 K 个升序链表
    //归并排序链表数组，最终实现两两合并链表
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return mergeKLists(lists, 0, lists.length - 1);
    }
    private ListNode mergeKLists(ListNode[] lists, int left, int right) {
        //只有一个链表时，有序，返回该列表的头节点
        if (left == right) return lists[left];
        //递归
        int mid = left + (right - left) / 2;
        ListNode node1 = mergeKLists(lists, left, mid);
        ListNode node2 = mergeKLists(lists, mid + 1, right);
        //合并
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        cur.next = node1 == null ? node2 : node1;
        return dummy.next;
    }

    //146. LRU 缓存
    class LRUCache {
        //需要一个hashmap记录数据
        //需要对key值按照使用的顺序排序：双向链表，队列等
        int capacity;
        HashMap<Integer, Integer> map;
        ArrayDeque<Integer> deque; //最近使用的数据放在队首
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<>();
            this.deque = new ArrayDeque<>();
        }

        public int get(int key) {
            if (map.containsKey(key)) {
                //最近使用了数据，放到队首
                deque.remove(key);
                deque.offerFirst(key);
                return map.get(key);
            } else {
                return -1;
            }
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                map.put(key, value);
                deque.remove(key);
            } else {
                if (map.size() == capacity) {
                    //新加入数据导致超出容量，删除队尾的数据
                    map.remove(deque.pollLast());
                }
                map.put(key, value);
            }
            //新加入的数据或者更新的数据都放在队首
            deque.offerFirst(key);
        }
    }
}

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
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372