hot100之链表下，

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)的复杂度就好了, 是什么呢, 好难猜啊