Reverse Nodes in k-Group · Deep Copy List with Random Pointer

Reverse Nodes in k-Group (LeetCode 25)

Reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k, left-out nodes in the end should remain as they are.

Key Insight: First check if there are at least k nodes. If so, reverse them and recursively process the rest.

ListNode reverseKGroup(ListNode head, int k) {
    ListNode cur = head;
    int count = 0;
    // 1. Move pointer to the k-th node
    while (cur != null && count < k) { 
        cur = cur.next; 
        count++; 
    }
    // If fewer than k nodes remain, do nothing
    if (count < k) return head;

    // 2. Reverse these k nodes
    ListNode prev = null, p = head;
    for (int i = 0; i < k; i++) {
        ListNode nextTemp = p.next;
        p.next = prev;
        prev = p;
        p = nextTemp;
    }
    
    // 3. Connect reversed unit to the result of original head (which is now tail)
    head.next = reverseKGroup(cur, k);
    
    return prev; // prev is the new head of this reversed unit
}

Iterative Version (Avoids recursion stack overflow):

ListNode reverseKGroupIterative(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode groupPrev = dummy;

    while (true) {
        ListNode kth = getKth(groupPrev, k);
        if (kth == null) break;

        ListNode groupNext = kth.next;
        // Reverse nodes in the range [groupPrev.next, kth]
        ListNode prev = groupNext;
        ListNode curr = groupPrev.next;
        while (curr != groupNext) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        ListNode temp = groupPrev.next;
        groupPrev.next = kth;
        groupPrev = temp; // Move groupPrev to the end of the newly reversed group
    }
    return dummy.next;
}

private ListNode getKth(ListNode curr, int k) {
    while (curr != null && k > 0) { 
        curr = curr.next; 
        k--; 
    }
    return curr;
}

Deep Copy List with Random Pointer (LeetCode 138)

Each node has an additional random pointer that could point to any node in the list or null.

Method 1: Hash Map (O(n) Space)

Node copyRandomList(Node head) {
    Map<Node, Node> map = new HashMap<>(); // Mapping: Original Node -> Cloned Node
    Node cur = head;
    
    // Pass 1: Create all cloned nodes
    while (cur != null) {
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    
    // Pass 2: Connect next and random pointers
    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);
}

Method 2: In-place Manipulation (O(1) Space, Three-Step Method)

1. Interweave: Create cloned nodes and insert each after its original: A → A' → B → B' → ...
2. Set Randoms: Set the random pointers of the cloned nodes using their original counter-parts.
3. Untangle: Separate the two lists.

Node copyRandomListO1(Node head) {
    if (head == null) return null;
    
    // 1. Interweave original and cloned nodes
    Node cur = head;
    while (cur != null) {
        Node cloned = new Node(cur.val);
        cloned.next = cur.next;
        cur.next = cloned;
        cur = cloned.next;
    }
    
    // 2. Set random pointers for cloned nodes
    cur = head;
    while (cur != null) {
        if (cur.random != null) {
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }
    
    // 3. Untangle into two separate lists
    Node dummyHead = new Node(0), cloneCur = dummyHead;
    cur = head;
    while (cur != null) {
        cloneCur.next = cur.next;
        cur.next = cur.next.next;
        cloneCur = cloneCur.next;
        cur = cur.next;
    }
    return dummyHead.next;
}

Method Comparison