hot100之链表下

K个一组翻转链表(025)

先看代码

class Solution {
 public ListNode reverseKGroup(ListNode head, int k) {
 ListNode dummy = new ListNode(-1, head);
 ListNode prev = dummy;
 while(prev.next != null){
 ListNode curr = reverse(prev, k);
 if (curr == null){
 reverse(prev, k);
 break;
 }
 prev = curr;
 }
 return dummy.next;
 }
 private ListNode reverse(ListNode prev, int k){
 ListNode curr = prev.next;
 int i = 1;
 for (;i < k && curr.next != null; i++){
 ListNode next = curr.next;
 curr.next = next.next;
 next.next = prev.next;
 prev.next = next;
 }
 return i < k ? null : curr;
 }
}

• 分析

重点在 reverse 部分

全局上prev 不动一直指向k个一组的起始部分, curr移动到k个一组末尾

单次中prev指向curr 指向的后一个节点, curr 向后移动

随机链表的复制(138)

先看代码

class Solution {
 public Node copyRandomList(Node head) {
 if (head == null){
 return null;
 }
 Map<Node, Node> map = new HashMap<>();
 Node curr = head;
 while (curr != null){
 map.put(curr, new Node(curr.val));
 curr = curr.next;
 }
 curr = head;
 while (curr != null){
 map.get(curr).next = map.get(curr.next);
 map.get(curr).random = map.get(curr.random);
 curr = curr.next;
 }
 return map.get(head);
 }
}

• 分析

题目的要求是要<深拷贝>一组链表(要求各节点地址不同)

难点在于以node.next为方向node.random 可能会指向未初始化节点

所以我们要先一步初始化复制的链表, 再在之后的遍历中把新node进一步拷贝

如何最高效的进一步拷贝node呢, 有O(1)的复杂度就好了, 是什么呢, 好难猜啊?

排序链表(148)

先看代码

class Solution {
 public ListNode sortList(ListNode head) {
 if (head == null || head.next == null){
 return head;
 }
 ListNode fast = head.next, slow = head;
 while (fast.next != null){
 fast = fast.next;
 slow = slow.next;
 if (fast.next != null){
 fast = fast.next;
 }
 }
 ListNode temp = slow.next;
 slow.next = null;
 ListNode lef = sortList(head);
 ListNode rig = sortList(temp);
 
 ListNode dummy = new ListNode(-1);
 ListNode res = dummy;
 while (lef != null && rig != null){
 if (lef.val < rig.val){
 dummy.next = lef;
 lef = lef.next;
 }else{
 dummy.next = rig;
 rig = rig.next;
 }
 dummy = dummy.next;
 }
 dummy.next = lef!=null ? lef : rig;
 return res.next;
 }
}

• 分析

根排序数组一样, 二分→排序→合并

• 踩坑

快慢指针在面对长度为2的链表, 没有快慢区分度 需要ListNode fast = head.next 让快指针先走一步

合并K个升序链表(023)

先看代码

class Solution {
 
 public ListNode mergeKLists(ListNode[] lists) {
 return mergeKLists(lists, 0, lists.length);
 }
 private ListNode mergeKLists(ListNode[] lists, int i, int j){
 int m = j - i;
 if (m == 0) return null;
 if (m == 1) return lists[i];
 ListNode lef = mergeKLists(lists, i, i + m/2);
 ListNode rig = mergeKLists(lists, i + m/2, j);
 return mergeTwoList(lef, rig);
 }
 private ListNode mergeTwoList() //实现同合并两个有序链表

• 分析

同样, 先对k个链表进行 K分→二分→排序→合并→K合

LRU缓存(146)

先看代码

 代码有点长 ,就不看了就看个总体吧
 
 private static class Node {
 int key, val;
 Node prev, next;
 Node (int k, int v){
 key = k;
 val = v;
 } 
 }
 private final int capacity;
 private final Node dummy = new Node(0,0);
 private final Map<Integer, Node> keyToNode = new HashMap<>();

• 分析

通过 HashMap保证O(1)的增删改查 链表来排序节点的新旧

利用prev, next 形成以dummy 为介质的环形链表