Problem

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Examples

Example 1:

---
title: Input
---
 graph LR
   A1[1]:::less --> B4[4]:::greater --> C3[3]:::pivot --> D2[2]:::less --> E5[5]:::greater --> F2[2]:::less
 
   classDef pivot fill:#ffb6c1,stroke:#000,stroke-width:2px;
   classDef less fill:#ffcc00,stroke:#000,stroke-width:2px;
   classDef greater fill:#add8e6,stroke:#000,stroke-width:2px;
  
---
title: Output
---
 graph LR
   A1[1]:::less --> D2[2]:::less --> F2[2]:::less --> B4[4]:::greater --> C3[3]:::pivot --> E5[5]:::greater
 
   classDef pivot fill:#ffb6c1,stroke:#000,stroke-width:2px;
   classDef less fill:#ffcc00,stroke:#000,stroke-width:2px;
   classDef greater fill:#add8e6,stroke:#000,stroke-width:2px;
  
1
2

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

Example 2:

---
title: Output
---
 graph LR
   A2[2]:::pivot --> B1[1]:::less
 
   classDef pivot fill:#ffb6c1,stroke:#000,stroke-width:2px;
   classDef less fill:#ffcc00,stroke:#000,stroke-width:2px;
  
---
title: Output
---
graph LR
   B1[1]:::less --> A2[2]:::pivot
 
   classDef pivot fill:#ffb6c1,stroke:#000,stroke-width:2px;
   classDef less fill:#ffcc00,stroke:#000,stroke-width:2px;
  
1
2

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

Solution

Method 1 - Use 2 Fake Pointers

Here is how we can solve it (take list as [1,4,3,2,5,2])

  1. Initialize Two Dummy Nodes:
    • Use two dummy nodes to maintain two separate lists: one for nodes less than x and one for nodes greater than or equal to x.
    • lessHead for nodes less than x and greaterHead for nodes greater than or equal to x.
  2. Traverse the List:
    • Traverse the linked list and partition the nodes into the two separate lists based on their values.
    • Connect nodes with values less than x to the less list.
    • Connect nodes with values greater than or equal to x to the greater list.
      • less = [1, 2, 2] and greater = [4, 3, 5]
    • Since we traverse the original linked list sequentially from left to right, the relative order of the nodes remains unchanged within each of the two partitions.
  3. Combine the Two Lists:
    • Attach the greater list to the end of the less list.
    • Ensure the last node of the combined list points to null.
      • output: [1, 2, 2, 4, 3, 5]
    • We did a dummy node initialization at the start to make implementation easier, you don’t want that to be part of the returned list, hence just move ahead one node in both the lists while combining the two list. Since both before and after have an extra node at the front.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
	public ListNode partition(ListNode head, int x) {
	    ListNode lessHead = new ListNode(0);
	    ListNode greaterHead = new ListNode(0);
	    ListNode less = lessHead, greater = greaterHead;
	
	    while (head != null) {
	        if (head.val < x) {
	            less.next = head;
	            less = less.next;
	        } else {
	            greater.next = head;
	            greater = greater.next;
	        }
	        head = head.next;
	    }
	
	    // Terminate the greater list
	    greater.next = null;
	    // Connect less list with greater list
	    less.next = greaterHead.next;
	
	    return lessHead.next;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        less_head = ListNode(0)
        greater_head = ListNode(0)
        less = less_head
        greater = greater_head

        while head:
            if head.val < x:
                less.next = head
                less = less.next
            else:
                greater.next = head
                greater = greater.next
            head = head.next

        # Terminate the greater list
        greater.next = None
        # Connect less list with greater list
        less.next = greater_head.next

        return less_head.next

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. The list is traversed once.
  • 🧺 Space complexity: O(1) as aux space, since only a constant amount of extra space is used for the pointers.

Note that we reuse nodes from the original linked list and reassign them to either the lessHead or greaterHead lists. This approach does not require extra space allocation for new nodes, as we are simply reordering the existing nodes. However, if the interviewer insists that the original list must remain unaltered, you can duplicate the nodes (by creating a new node) and perform operations on the new copies.