Rotate a Doubly Linked list in group of Given Size

The problem, simply

You get a doubly linked list, where every box has a next arrow forward and a prev arrow back, and a number k.

Walk the chain in groups of k boxes and turn each group around. The groups stay in their old order. If the last group has fewer than k boxes, turn it around too. Every next and every prev must be right at the end, and the new head must have prev = null.

The sheet calls this "rotate in groups", but the task it points to is turning each group around (reversing it), as in the examples.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do not touch the arrows. For each group, copy its numbers into a small list, turn the list around, and write the numbers back into the same boxes.

1. Start at the head.
2. Copy up to k numbers into a small list and remember where the group started.
3. Turn the small list around and write the numbers back into the group's boxes.
4. Go on with the next group.

import java.util.*;

class Solution {
    public Node reverseInGroups(Node head, int k) {
        Node curr = head;
        while (curr != null) {
            Node groupStart = curr;
            List<Integer> nums = new ArrayList<>();
            for (int i = 0; i < k && curr != null; i++) {   // copy up to k numbers
                nums.add(curr.data);
                curr = curr.next;
            }
            Collections.reverse(nums);
            Node w = groupStart;
            for (int x : nums) { w.data = x; w = w.next; }  // write them back
        }
        return head;
    }
}

How long it takes: every box is read once and written once, O(n). Extra room: the small list holds one group, O(k). Interviewers usually want the boxes moved, not the numbers.

Way 2: the clever way

Turn the boxes themselves around, one group at a time, and stitch the groups together.

1. curr walks the chain. prevTail is the last box of the finished part, null at first.
2. Remember groupFirst = curr. Turn up to k boxes around: for each box, save next, point next back to prev, and point prev forward to the saved next.
3. Now prev is the group's new first box and groupFirst is its new last box.
4. Stitch: if this is the first group, it gives the new head. Otherwise prevTail.next = prev. In both cases set prev.prev = prevTail.
5. Move prevTail to groupFirst and keep going while curr is not null.

class Solution {
    public Node reverseInGroups(Node head, int k) {
        if (head == null || k <= 1) return head;
        Node newHead = null, prevTail = null, curr = head;
        while (curr != null) {
            Node groupFirst = curr, prev = null;
            for (int i = 0; i < k && curr != null; i++) {   // turn up to k boxes around
                Node next = curr.next;
                curr.next = prev;          // look back
                curr.prev = next;          // the old next is now behind me
                prev = curr;
                curr = next;
            }
            // prev is the group's new first box, groupFirst its new last box
            if (newHead == null) newHead = prev;
            else prevTail.next = prev;     // stitch forward
            prev.prev = prevTail;          // stitch backward (null for the first group)
            prevTail = groupFirst;
        }
        return newHead;
    }
}

How long it takes: every box is flipped once, O(n). Extra room: a few fingers, O(1). The last box of the last group already has next = null, because each group starts flipping with prev = null.

Watch out for

• Stitching only next between groups. Walking backwards from the tail then jumps to the wrong box. Fix both prevTail.next and prev.prev.
• Moving prevTail to prev. After the flip, prev is the front of the group. The back is groupFirst.
• Read the problem: some versions leave the short last group alone. Then count k boxes first and stop if there are not enough, as in the singly linked version.

What interviewers ask next

• How is this different from the singly linked version? Same groups, but every flip and every stitch must fix two arrows, and the head's prev must end as null.
• Rotate each group instead of reversing it: in each block of k, move the last d boxes to the front of the block. Cut the block, find its dth box from the end, and relink the block's two pieces in swapped order.
• Do it with recursion: flip the first group, then let a helper do the rest and stitch the group's last box to the helper's head in both directions. It costs O(n/k) stack room.
• How do you test it? Walk forward from the head and backward from the tail. The two readings must be exact mirrors, and the head's prev and the tail's next must be null.

Remember this

Grown-up words: the dance line is a doubly linked list, each kid is a node with prev and next pointers, turning a little line around is reversing a group, and stitching the gaps is relinking the group boundaries.