Leetcode 86: Partition List

 

1. Problem Statement (Simple Explanation)

You’re given:

• The head of a singly linked list.

• An integer x.

You must rearrange the list so that:

• All nodes with value < x come before nodes with value >= x.

• Within each group (< x and >= x), relative order of nodes must be preserved (stable partition).

• Return the head of the new list.

You must do this by re-linking nodes (no need to allocate new nodes, just moving pointers).

2. Examples

Example 1:

Input: head = [1,4,3,2,5,2], x = 3

Nodes < 3: 1,2,2
Nodes >= 3: 4,3,5

Preserving original order within each group:

• < 3 group in original order: 1,2,2

• >= 3 group in original order: 4,3,5

Concatenate: 1 → 2 → 2 → 4 → 3 → 5

Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2

• < 2 group: 1

• >= 2 group: 2

Result: [1,2].

Output: [1,2]

3. Approach – Two Lists (Less & Greater-or-Equal), Then Concatenate (O(n))

We walk through the original list once and split nodes into two separate lists:

1. A list before for nodes with val < x.

2. A list after for nodes with val >= x.

We preserve original order by always appending to the tail of the corresponding list.

At the end, we link:

before_tail.next = after_head

after_tail.next = null

And return before_head (or after_head if before is empty).

To simplify handling of empty lists and head changes, we use dummy nodes:

• beforeDummy → head of the < x list.

• afterDummy → head of the >= x list.

Algorithm (Step-by-Step):

1. If head == null, return null.

2. Create dummy nodes:

beforeDummy = new ListNode(0)

afterDummy  = new ListNode(0)

3. Set pointers:

before = beforeDummy

after  = afterDummy

curr   = head

4. Traverse the original list:

• For each node curr:

• If curr.val < x:

• before.next = curr

• before = before.next

• Else:

• after.next = curr

• after = after.next

• Move curr = curr.next (but we must be careful not to lose next pointer; see code).

5. Terminate after list:

after.next = null

6. Connect before and after lists:

before.next = afterDummy.next

7. Return beforeDummy.next.

Pseudo-code:

Complexity:

Let n be the number of nodes:

• Time: O(n) – single pass through the list.

• Extra space: O(1) – only a few pointers (dummy nodes, etc.).

4. Java code

5. C++ code

6. C code

7. Python code

8. JavaScript code