Linked List Group Reverse

JavaView on GFG

Time: O(n)

Space: O(n/k)

Intuition

Reverse every k nodes. For each group of k, reverse the sublist then connect to next group.

Algorithm

1Check if at least k nodes remain; if not, leave as-is.
2Reverse k nodes using prev/curr/next.
3head.next = reverseKGroup(next_group, k).
4Return new head of this group.

Common Pitfalls

•After reversal, old head of group becomes the tail. Connect it to recursively processed next group.

Linked List Group Reverse.java

Java

// Approach: Reverse nodes in groups of k. Recursively reverse each group and connect to next.
// Time: O(n) Space: O(n/k)
class Node {
    int data;
    Node next;

    Node(int key) {
        data = key;
        next = null;
    }
}

class Solution {
    public static Node reverseKGroup(Node head, int k) {
        Node curr = head, prev = null;
        while (curr != null) {
            Node nth = findNth(curr, k);
            if (nth == null) {
                Node rev = reverseList(curr);
                if (prev != null)
                    prev.next = rev;
                else
                    return rev;
                break;
            }
            Node nthNext = nth.next;
            nth.next = null;
            Node rhead = reverseList(curr);
            if (curr == head)
                head = rhead;
            else
                prev.next = rhead;
            prev = curr;
            curr = nthNext;
        }
        return head;
    }

    private static Node findNth(Node curr, int n) {
        for (int i = 0; i < n - 1; i++) {
            if (curr == null)
                return null;
            curr = curr.next;
        }
        return curr;
    }

    private static Node reverseList(Node curr) {
        Node prev = null, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Was this solution helpful?