Rearrange Linked List

Tags

Rearrange Linked List

Category

Linked Lists

Difficulty

Hard

Problem Statement

Given a singly linked list and an integer pivot value k, rearrange the linked list so that all nodes with values less than k come first, followed by all nodes with values equal to k, followed by all nodes with values greater than k. The relative order of nodes within each partition should be preserved (stable partition). The rearrangement should be done in place.

Intuition

This is a three-way partition of a linked list, similar to the Dutch National Flag problem on arrays. We can create three separate lists (less than, equal to, greater than) by traversing the original list once, then concatenate them. Since we are rearranging existing nodes (not creating new ones), this uses O(1) extra space beyond a few pointers.

Approach

  1. Initialize three pairs of pointers: (lessHead, lessTail), (equalHead, equalTail), and (greaterHead, greaterTail), all set to null.
  2. Traverse the original linked list node by node.
  3. For each node, compare its value to k and append it to the appropriate partition list.
  4. After traversal, concatenate the three lists: less -> equal -> greater.
  5. Handle cases where one or more partitions are empty.
  6. Set the next pointer of the last node in the combined list to null.
  7. Return the head of the combined list.

Pseudocode

function rearrangeLinkedList(head, k):
    lessHead = lessTail = null
    equalHead = equalTail = null
    greaterHead = greaterTail = null

    current = head
    while current is not null:
        nextNode = current.next
        current.next = null

        if current.value < k:
            if lessHead is null:
                lessHead = lessTail = current
            else:
                lessTail.next = current
                lessTail = current

        else if current.value == k:
            if equalHead is null:
                equalHead = equalTail = current
            else:
                equalTail.next = current
                equalTail = current

        else:
            if greaterHead is null:
                greaterHead = greaterTail = current
            else:
                greaterTail.next = current
                greaterTail = current

        current = nextNode

    // Connect partitions
    head = connectPartitions(lessHead, lessTail, equalHead, equalTail, greaterHead, greaterTail)
    return head

function connectPartitions(lH, lT, eH, eT, gH, gT):
    // Connect less -> equal -> greater, skipping empty partitions
    if lT is not null:
        lT.next = eH if eH is not null else gH
    if eT is not null:
        eT.next = gH

    firstHead = lH if lH is not null else (eH if eH is not null else gH)
    return firstHead

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Single pass through the list plus constant-time concatenation.
  • Space: O(1) extra space. Only a fixed number of pointers are used; no new nodes are created.

Key Insights

  • Maintaining both head and tail pointers for each partition enables O(1) appending and O(1) concatenation.
  • Detaching each node (current.next = null) before appending prevents cycles in the rearranged list.
  • The algorithm is stable — nodes within each partition maintain their original relative order.
  • This is analogous to the partition step of quicksort but on a linked list with three-way partitioning.
  • The pivot value k does not need to be present in the list.

Edge Cases

  • The list is empty — return null.
  • All nodes have the same value — the list is unchanged.
  • No nodes equal to k — the equal partition is empty and is skipped during concatenation.
  • Only one partition is non-empty — the list is already correctly arranged.
  • k is smaller than all values or larger than all values — one of the extreme partitions gets all nodes.
  • The list has only one node — return it unchanged.

Linked mentions