Partition List

Problem Statement

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

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

Examples

Input	x	Output	Explanation
`[1, 4, 3, 2, 5, 2]`	`3`	`[1, 2, 2, 4, 3, 5]`	All nodes < 3 move left; >= 3 stay right. Order preserved.
`[2, 1]`	`2`	`[1, 2]`	Only 1 < 2, so it goes first; 2 stays.
`[5, 3, 1, 4, 2]`	`3`	`[1, 2, 5, 3, 4]`	[1, 2] < 3, then [5, 3, 4] >= 3.

Constraints

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Real-World Applications

Complexity Comparison

Approach	Time	Space	Method	Best When
Two List Heads	O(n)	O(1)	Build two separate lists, merge	General case — clean, easy to understand
Single List Rearrange	O(n)	O(1)	Rearrange nodes in place	Memory ultra-constrained, prefers single list

* Both use O(1) extra space (two or more dummy/pointer nodes).

Which approach should you learn first?

Pick Two List Heads if you want clarity and correctness. It is easier to reason about and less error-prone.
Pick Single List Rearrange if you want to practice advanced pointer manipulation or face extreme space constraints.

Clearest Logic

Two List Heads

O(n) time · O(1) space

Advanced Pointers

Single Rearrange

O(n) time · O(1) space

Approach 1: Two List Heads (Recommended)

★ Recommended

Build two separate lists — one for nodes < x, one for nodes >= x — then connect them.

The key idea is simplicity: create two independent lists as you traverse, then splice them together. This avoids the complexity of tracking multiple pointers in one list.

⏱ Time O(n) Single pass through list 💾 Space O(1) Only pointer variables

Step-by-step Example

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

Step	current.val	< 3?	Action	smaller list	larger list
1	1	✓	Append to smaller	1	—
2	4	✗	Append to larger	1	4
3	3	✗	Append to larger	1	4 → 3
4	2	✓	Append to smaller	1 → 2	4 → 3
5	5	✗	Append to larger	1 → 2	4 → 3 → 5
6	2	✓	Append to smaller	1 → 2 → 2	4 → 3 → 5
—	—	—	Merge: smaller.next = larger	1 → 2 → 2 → 4 → 3 → 5	—

Step 1 of 8 Target: partition

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function partitionTwoHeads(head, x):
    smaller_dummy = new ListNode(0)
    larger_dummy = new ListNode(0)

    smaller_ptr = smaller_dummy
    larger_ptr = larger_dummy

    current = head
    while current:
        if current.val < x:
            smaller_ptr.next = current
            smaller_ptr = smaller_ptr.next
        else:
            larger_ptr.next = current
            larger_ptr = larger_ptr.next
        current = current.next

    // Close the larger list
    larger_ptr.next = null

    // Connect the two lists
    smaller_ptr.next = larger_dummy.next

    return smaller_dummy.next

Solution Code

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def partition_list_two_heads(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    """
    Partition linked list into two groups: values < x and values >= x.
    Uses two separate list heads and merges them at the end.

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(1) excluding the output list
    """
    # Create dummy nodes for two lists
    smaller_dummy = ListNode(0)
    larger_dummy = ListNode(0)

    # Pointers to build the two lists
    smaller_ptr = smaller_dummy
    larger_ptr = larger_dummy

    # Partition nodes into two lists
    current = head
    while current:
        if current.val < x:
            smaller_ptr.next = current
            smaller_ptr = smaller_ptr.next
        else:
            larger_ptr.next = current
            larger_ptr = larger_ptr.next
        current = current.next

    # Close the larger list to avoid cycles
    larger_ptr.next = None

    # Connect the two lists
    smaller_ptr.next = larger_dummy.next

    return smaller_dummy.next


# Helper function to create a linked list from a list
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Helper function to convert linked list to list for easy testing
def linked_list_to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result


# Test cases
head = create_linked_list([1, 4, 3, 2, 5, 2])
result = partition_list_two_heads(head, 3)
print(linked_list_to_list(result))  # [1, 2, 2, 4, 3, 5]

head = create_linked_list([2, 1])
result = partition_list_two_heads(head, 2)
print(linked_list_to_list(result))  # [1, 2]

head = create_linked_list([5, 3, 1, 4, 2])
result = partition_list_two_heads(head, 3)
print(linked_list_to_list(result))  # [1, 2, 5, 3, 4]

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

/**
 * Partition linked list into two groups: values < x and values >= x.
 * Uses two separate list heads and merges them at the end.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(1) excluding the output list
 */
ListNode* partitionListTwoHeads(ListNode* head, int x) {
    // Create dummy nodes for two lists
    ListNode* smaller_dummy = new ListNode(0);
    ListNode* larger_dummy = new ListNode(0);

    // Pointers to build the two lists
    ListNode* smaller_ptr = smaller_dummy;
    ListNode* larger_ptr = larger_dummy;

    // Partition nodes into two lists
    ListNode* current = head;
    while (current) {
        if (current->val < x) {
            smaller_ptr->next = current;
            smaller_ptr = smaller_ptr->next;
        } else {
            larger_ptr->next = current;
            larger_ptr = larger_ptr->next;
        }
        current = current->next;
    }

    // Close the larger list to avoid cycles
    larger_ptr->next = nullptr;

    // Connect the two lists
    smaller_ptr->next = larger_dummy->next;

    return smaller_dummy->next;
}

// Helper function to create a linked list from a vector
ListNode* createLinkedList(const vector<int>& values) {
    if (values.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (size_t i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print linked list
void printLinkedList(ListNode* node) {
    cout << "[";
    while (node) {
        cout << node->val;
        if (node->next) cout << ", ";
        node = node->next;
    }
    cout << "]" << endl;
}

// Test cases
int main() {
    ListNode* head = createLinkedList({1, 4, 3, 2, 5, 2});
    ListNode* result = partitionListTwoHeads(head, 3);
    printLinkedList(result);  // [1, 2, 2, 4, 3, 5]

    head = createLinkedList({2, 1});
    result = partitionListTwoHeads(head, 2);
    printLinkedList(result);  // [1, 2]

    head = createLinkedList({5, 3, 1, 4, 2});
    result = partitionListTwoHeads(head, 3);
    printLinkedList(result);  // [1, 2, 5, 3, 4]

    return 0;
}

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class partition_list_two_heads {
    /**
     * Partition linked list into two groups: values < x and values >= x.
     * Uses two separate list heads and merges them at the end.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(1) excluding the output list
     */
    public static ListNode partitionListTwoHeads(ListNode head, int x) {
        // Create dummy nodes for two lists
        ListNode smaller_dummy = new ListNode(0);
        ListNode larger_dummy = new ListNode(0);

        // Pointers to build the two lists
        ListNode smaller_ptr = smaller_dummy;
        ListNode larger_ptr = larger_dummy;

        // Partition nodes into two lists
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                smaller_ptr.next = current;
                smaller_ptr = smaller_ptr.next;
            } else {
                larger_ptr.next = current;
                larger_ptr = larger_ptr.next;
            }
            current = current.next;
        }

        // Close the larger list to avoid cycles
        larger_ptr.next = null;

        // Connect the two lists
        smaller_ptr.next = larger_dummy.next;

        return smaller_dummy.next;
    }

    // Helper function to create a linked list from an array
    public static ListNode createLinkedList(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to list for easy testing
    public static List<Integer> linkedListToList(ListNode node) {
        List<Integer> result = new ArrayList<>();
        while (node != null) {
            result.add(node.val);
            node = node.next;
        }
        return result;
    }

    // Test cases
    public static void main(String[] args) {
        ListNode head = createLinkedList(new int[]{1, 4, 3, 2, 5, 2});
        ListNode result = partitionListTwoHeads(head, 3);
        System.out.println(linkedListToList(result));  // [1, 2, 2, 4, 3, 5]

        head = createLinkedList(new int[]{2, 1});
        result = partitionListTwoHeads(head, 2);
        System.out.println(linkedListToList(result));  // [1, 2]

        head = createLinkedList(new int[]{5, 3, 1, 4, 2});
        result = partitionListTwoHeads(head, 3);
        System.out.println(linkedListToList(result));  // [1, 2, 5, 3, 4]
    }
}

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Partition linked list into two groups: values < x and values >= x.
 * Uses two separate list heads and merges them at the end.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(1) excluding the output list
 */
function partitionListTwoHeads(head, x) {
    // Create dummy nodes for two lists
    const smaller_dummy = new ListNode(0);
    const larger_dummy = new ListNode(0);

    // Pointers to build the two lists
    let smaller_ptr = smaller_dummy;
    let larger_ptr = larger_dummy;

    // Partition nodes into two lists
    let current = head;
    while (current) {
        if (current.val < x) {
            smaller_ptr.next = current;
            smaller_ptr = smaller_ptr.next;
        } else {
            larger_ptr.next = current;
            larger_ptr = larger_ptr.next;
        }
        current = current.next;
    }

    // Close the larger list to avoid cycles
    larger_ptr.next = null;

    // Connect the two lists
    smaller_ptr.next = larger_dummy.next;

    return smaller_dummy.next;
}

// Helper function to create a linked list from an array
function createLinkedList(values) {
    if (values.length === 0) {
        return null;
    }
    let head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for easy testing
function linkedListToArray(node) {
    const result = [];
    while (node) {
        result.push(node.val);
        node = node.next;
    }
    return result;
}

// Test cases
let head = createLinkedList([1, 4, 3, 2, 5, 2]);
let result = partitionListTwoHeads(head, 3);
console.log(linkedListToArray(result));  // [1, 2, 2, 4, 3, 5]

head = createLinkedList([2, 1]);
result = partitionListTwoHeads(head, 2);
console.log(linkedListToArray(result));  // [1, 2]

head = createLinkedList([5, 3, 1, 4, 2]);
result = partitionListTwoHeads(head, 3);
console.log(linkedListToArray(result));  // [1, 2, 5, 3, 4]

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/// Partition linked list into two groups: values < x and values >= x.
/// Uses two separate list heads and merges them at the end.
///
/// Time Complexity: O(n) where n is the number of nodes
/// Space Complexity: O(1) excluding the output list
pub fn partition(
    head: Option<Rc<RefCell<ListNode>>>,
    x: i32,
) -> Option<Rc<RefCell<ListNode>>> {
    // Create dummy nodes for two lists
    let mut smaller_dummy = Box::new(ListNode::new(0));
    let mut larger_dummy = Box::new(ListNode::new(0));

    // Pointers to build the two lists
    let mut smaller_ptr = &mut smaller_dummy.next;
    let mut larger_ptr = &mut larger_dummy.next;

    // Partition nodes into two lists
    let mut current = head;
    while let Some(node) = current {
        let next = node.borrow_mut().next.take();
        if node.borrow().val < x {
            *smaller_ptr = Some(node);
            smaller_ptr = &mut smaller_ptr.as_mut().unwrap().borrow_mut().next;
        } else {
            *larger_ptr = Some(node);
            larger_ptr = &mut larger_ptr.as_mut().unwrap().borrow_mut().next;
        }
        current = next;
    }

    // Connect the two lists
    *smaller_ptr = larger_dummy.next;

    smaller_dummy.next
}

// Helper function to create a linked list from a vector
fn create_linked_list(values: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if values.is_empty() {
        return None;
    }
    let mut head = ListNode::new(values[0]);
    let mut current = &mut head;
    for val in &values[1..] {
        let new_node = ListNode::new(*val);
        current.next = Some(Rc::new(RefCell::new(new_node)));
        current = &mut current.next.as_mut().unwrap().borrow_mut();
    }
    Some(Rc::new(RefCell::new(head)))
}

// Helper function to convert linked list to vector for easy testing
fn linked_list_to_vec(node: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = node;
    while let Some(node) = current {
        result.push(node.borrow().val);
        current = node.borrow_mut().next.take();
    }
    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_partition_list() {
        let head = create_linked_list(vec![1, 4, 3, 2, 5, 2]);
        let result = partition(head, 3);
        assert_eq!(linked_list_to_vec(result), vec![1, 2, 2, 4, 3, 5]);

        let head = create_linked_list(vec![2, 1]);
        let result = partition(head, 2);
        assert_eq!(linked_list_to_vec(result), vec![1, 2]);

        let head = create_linked_list(vec![5, 3, 1, 4, 2]);
        let result = partition(head, 3);
        assert_eq!(linked_list_to_vec(result), vec![1, 2, 5, 3, 4]);
    }
}

fn main() {
    let head = create_linked_list(vec![1, 4, 3, 2, 5, 2]);
    let result = partition(head, 3);
    println!("{:?}", linked_list_to_vec(result));  // [1, 2, 2, 4, 3, 5]

    let head = create_linked_list(vec![2, 1]);
    let result = partition(head, 2);
    println!("{:?}", linked_list_to_vec(result));  // [1, 2]

    let head = create_linked_list(vec![5, 3, 1, 4, 2]);
    let result = partition(head, 3);
    println!("{:?}", linked_list_to_vec(result));  // [1, 2, 5, 3, 4]
}

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

// Partition linked list into two groups: values < x and values >= x.
// Uses two separate list heads and merges them at the end.
//
// Time Complexity: O(n) where n is the number of nodes
// Space Complexity: O(1) excluding the output list
func partitionListTwoHeads(head *ListNode, x int) *ListNode {
  // Create dummy nodes for two lists
  smallerDummy := &ListNode{Val: 0}
  largerDummy := &ListNode{Val: 0}

  // Pointers to build the two lists
  smallerPtr := smallerDummy
  largerPtr := largerDummy

  // Partition nodes into two lists
  current := head
  for current != nil {
    if current.Val < x {
      smallerPtr.Next = current
      smallerPtr = smallerPtr.Next
    } else {
      largerPtr.Next = current
      largerPtr = largerPtr.Next
    }
    current = current.Next
  }

  // Close the larger list to avoid cycles
  largerPtr.Next = nil

  // Connect the two lists
  smallerPtr.Next = largerDummy.Next

  return smallerDummy.Next
}

// Helper function to create a linked list from a slice
func createLinkedList(values []int) *ListNode {
  if len(values) == 0 {
    return nil
  }
  head := &ListNode{Val: values[0]}
  current := head
  for i := 1; i < len(values); i++ {
    current.Next = &ListNode{Val: values[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for easy testing
func linkedListToSlice(node *ListNode) []int {
  result := []int{}
  for node != nil {
    result = append(result, node.Val)
    node = node.Next
  }
  return result
}

// Test cases
func main() {
  head := createLinkedList([]int{1, 4, 3, 2, 5, 2})
  result := partitionListTwoHeads(head, 3)
  fmt.Println(linkedListToSlice(result))  // [1 2 2 4 3 5]

  head = createLinkedList([]int{2, 1})
  result = partitionListTwoHeads(head, 2)
  fmt.Println(linkedListToSlice(result))  // [1 2]

  head = createLinkedList([]int{5, 3, 1, 4, 2})
  result = partitionListTwoHeads(head, 3)
  fmt.Println(linkedListToSlice(result))  // [1 2 5 3 4]
}

Approach 2: Single List Rearrange

🎯 Interview Favourite

Rearrange nodes in a single pass by removing nodes with value < x from their current position and inserting them before the partition boundary.

This approach is more complex but demonstrates mastery of pointer manipulation. Instead of building separate lists, it rearranges the original list in place.

⏱ Time O(n) Single pass through list 💾 Space O(1) Only pointer variables

Step-by-step Example

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

Phase 1: Find the partition point (first node >= x)

Start: 1 (< 3), 4 (>= 3) ← partition starts here

Phase 2: Rearrange nodes after partition

See 2 (< 3 but after partition), move before partition: 1 → 2 → 4 → 3 → 5 → 2
See 2 (< 3 but after partition), move before partition: 1 → 2 → 2 → 4 → 3 → 5
Final: 1 → 2 → 2 → 4 → 3 → 5

Pseudocode

function partitionSingleRearrange(head, x):
    dummy = new ListNode(0)
    dummy.next = head

    // Find partition point
    prev = dummy
    current = head
    while current and current.val < x:
        prev = current
        current = current.next

    // If all nodes < x or list empty, return
    if not current:
        return dummy.next

    // Rearrange nodes < x found after partition
    partition_prev = prev
    run = current

    while run:
        if run.val < x:
            // Remove from current position
            current.next = run.next

            // Insert before partition
            run.next = partition_prev.next
            partition_prev.next = run
            partition_prev = run

            run = current.next
        else:
            current = run
            run = run.next

    return dummy.next

Solution Code

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def partition_list_single_rearrange(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    """
    Partition linked list into two groups: values < x and values >= x.
    Rearranges nodes in a single pass without creating separate lists.

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(1) excluding the output list
    """
    # Create a dummy node to simplify edge cases
    dummy = ListNode(0)
    dummy.next = head

    # Find the node just before the partition point
    prev = dummy
    current = head

    while current and current.val < x:
        prev = current
        current = current.next

    # Now prev is the last node with value < x (or dummy if all nodes >= x)
    # current is the first node with value >= x (or None if all nodes < x)

    # If all nodes are less than x or list is empty, return as is
    if not current:
        return dummy.next

    # Now we need to insert nodes with value < x before the partition point
    partition_prev = prev  # Last node of < x group
    run = current  # Start from the partition point

    while run:
        if run.val < x:
            # Remove run from its position
            current.next = run.next

            # Insert run before the partition point
            run.next = partition_prev.next
            partition_prev.next = run

            # Move partition_prev forward
            partition_prev = run

            # Current stays the same to check the next node
            run = current.next
        else:
            # Move forward
            current = run
            run = run.next

    return dummy.next


# Helper function to create a linked list from a list
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Helper function to convert linked list to list for easy testing
def linked_list_to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result


# Test cases
head = create_linked_list([1, 4, 3, 2, 5, 2])
result = partition_list_single_rearrange(head, 3)
print(linked_list_to_list(result))  # [1, 2, 2, 4, 3, 5]

head = create_linked_list([2, 1])
result = partition_list_single_rearrange(head, 2)
print(linked_list_to_list(result))  # [1, 2]

head = create_linked_list([5, 3, 1, 4, 2])
result = partition_list_single_rearrange(head, 3)
print(linked_list_to_list(result))  # [1, 2, 5, 3, 4]

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

/**
 * Partition linked list into two groups: values < x and values >= x.
 * Rearranges nodes in a single pass without creating separate lists.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(1) excluding the output list
 */
ListNode* partitionListSingleRearrange(ListNode* head, int x) {
    // Create a dummy node to simplify edge cases
    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    // Find the node just before the partition point
    ListNode* prev = dummy;
    ListNode* current = head;

    while (current && current->val < x) {
        prev = current;
        current = current->next;
    }

    // Now prev is the last node with value < x (or dummy if all nodes >= x)
    // current is the first node with value >= x (or nullptr if all nodes < x)

    // If all nodes are less than x or list is empty, return as is
    if (!current) {
        return dummy->next;
    }

    // Now we need to insert nodes with value < x before the partition point
    ListNode* partition_prev = prev;  // Last node of < x group
    ListNode* run = current;  // Start from the partition point

    while (run) {
        if (run->val < x) {
            // Remove run from its position
            current->next = run->next;

            // Insert run before the partition point
            run->next = partition_prev->next;
            partition_prev->next = run;

            // Move partition_prev forward
            partition_prev = run;

            // Current stays the same to check the next node
            run = current->next;
        } else {
            // Move forward
            current = run;
            run = run->next;
        }
    }

    return dummy->next;
}

// Helper function to create a linked list from a vector
ListNode* createLinkedList(const vector<int>& values) {
    if (values.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (size_t i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to print linked list
void printLinkedList(ListNode* node) {
    cout << "[";
    while (node) {
        cout << node->val;
        if (node->next) cout << ", ";
        node = node->next;
    }
    cout << "]" << endl;
}

// Test cases
int main() {
    ListNode* head = createLinkedList({1, 4, 3, 2, 5, 2});
    ListNode* result = partitionListSingleRearrange(head, 3);
    printLinkedList(result);  // [1, 2, 2, 4, 3, 5]

    head = createLinkedList({2, 1});
    result = partitionListSingleRearrange(head, 2);
    printLinkedList(result);  // [1, 2]

    head = createLinkedList({5, 3, 1, 4, 2});
    result = partitionListSingleRearrange(head, 3);
    printLinkedList(result);  // [1, 2, 5, 3, 4]

    return 0;
}

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class partition_list_single_rearrange {
    /**
     * Partition linked list into two groups: values < x and values >= x.
     * Rearranges nodes in a single pass without creating separate lists.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(1) excluding the output list
     */
    public static ListNode partitionListSingleRearrange(ListNode head, int x) {
        // Create a dummy node to simplify edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // Find the node just before the partition point
        ListNode prev = dummy;
        ListNode current = head;

        while (current != null && current.val < x) {
            prev = current;
            current = current.next;
        }

        // Now prev is the last node with value < x (or dummy if all nodes >= x)
        // current is the first node with value >= x (or null if all nodes < x)

        // If all nodes are less than x or list is empty, return as is
        if (current == null) {
            return dummy.next;
        }

        // Now we need to insert nodes with value < x before the partition point
        ListNode partition_prev = prev;  // Last node of < x group
        ListNode run = current;  // Start from the partition point

        while (run != null) {
            if (run.val < x) {
                // Remove run from its position
                current.next = run.next;

                // Insert run before the partition point
                run.next = partition_prev.next;
                partition_prev.next = run;

                // Move partition_prev forward
                partition_prev = run;

                // Current stays the same to check the next node
                run = current.next;
            } else {
                // Move forward
                current = run;
                run = run.next;
            }
        }

        return dummy.next;
    }

    // Helper function to create a linked list from an array
    public static ListNode createLinkedList(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to list for easy testing
    public static List<Integer> linkedListToList(ListNode node) {
        List<Integer> result = new ArrayList<>();
        while (node != null) {
            result.add(node.val);
            node = node.next;
        }
        return result;
    }

    // Test cases
    public static void main(String[] args) {
        ListNode head = createLinkedList(new int[]{1, 4, 3, 2, 5, 2});
        ListNode result = partitionListSingleRearrange(head, 3);
        System.out.println(linkedListToList(result));  // [1, 2, 2, 4, 3, 5]

        head = createLinkedList(new int[]{2, 1});
        result = partitionListSingleRearrange(head, 2);
        System.out.println(linkedListToList(result));  // [1, 2]

        head = createLinkedList(new int[]{5, 3, 1, 4, 2});
        result = partitionListSingleRearrange(head, 3);
        System.out.println(linkedListToList(result));  // [1, 2, 5, 3, 4]
    }
}

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Partition linked list into two groups: values < x and values >= x.
 * Rearranges nodes in a single pass without creating separate lists.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(1) excluding the output list
 */
function partitionListSingleRearrange(head, x) {
    // Create a dummy node to simplify edge cases
    const dummy = new ListNode(0);
    dummy.next = head;

    // Find the node just before the partition point
    let prev = dummy;
    let current = head;

    while (current && current.val < x) {
        prev = current;
        current = current.next;
    }

    // Now prev is the last node with value < x (or dummy if all nodes >= x)
    // current is the first node with value >= x (or null if all nodes < x)

    // If all nodes are less than x or list is empty, return as is
    if (!current) {
        return dummy.next;
    }

    // Now we need to insert nodes with value < x before the partition point
    let partition_prev = prev;  // Last node of < x group
    let run = current;  // Start from the partition point

    while (run) {
        if (run.val < x) {
            // Remove run from its position
            current.next = run.next;

            // Insert run before the partition point
            run.next = partition_prev.next;
            partition_prev.next = run;

            // Move partition_prev forward
            partition_prev = run;

            // Current stays the same to check the next node
            run = current.next;
        } else {
            // Move forward
            current = run;
            run = run.next;
        }
    }

    return dummy.next;
}

// Helper function to create a linked list from an array
function createLinkedList(values) {
    if (values.length === 0) {
        return null;
    }
    let head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for easy testing
function linkedListToArray(node) {
    const result = [];
    while (node) {
        result.push(node.val);
        node = node.next;
    }
    return result;
}

// Test cases
let head = createLinkedList([1, 4, 3, 2, 5, 2]);
let result = partitionListSingleRearrange(head, 3);
console.log(linkedListToArray(result));  // [1, 2, 2, 4, 3, 5]

head = createLinkedList([2, 1]);
result = partitionListSingleRearrange(head, 2);
console.log(linkedListToArray(result));  // [1, 2]

head = createLinkedList([5, 3, 1, 4, 2]);
result = partitionListSingleRearrange(head, 3);
console.log(linkedListToArray(result));  // [1, 2, 5, 3, 4]

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/// Partition linked list into two groups: values < x and values >= x.
/// Rearranges nodes in a single pass without creating separate lists.
///
/// Time Complexity: O(n) where n is the number of nodes
/// Space Complexity: O(1) excluding the output list
pub fn partition(
    head: Option<Rc<RefCell<ListNode>>>,
    x: i32,
) -> Option<Rc<RefCell<ListNode>>> {
    // Create a dummy node to simplify edge cases
    let mut dummy = Box::new(ListNode::new(0));
    dummy.next = head;

    let mut dummy_ref = dummy;
    let mut prev = &mut dummy_ref as *mut Box<ListNode>;
    let mut current = unsafe { &mut (*prev).next };

    // Find the node just before the partition point
    while let Some(ref mut node) = *current {
        if node.borrow().val < x {
            prev = &mut **current as *mut _;
            current = &mut node.borrow_mut().next;
        } else {
            break;
        }
    }

    // If all nodes are less than x or list is empty, return as is
    if current.is_none() {
        return dummy_ref.next;
    }

    // Now we need to insert nodes with value < x before the partition point
    let mut partition_prev = prev;
    let mut run = current;

    while let Some(ref mut node) = *run {
        if node.borrow().val < x {
            // Remove run from its position
            let node_next = node.borrow_mut().next.take();
            *current = node_next;

            // Insert run before the partition point
            unsafe {
                let partition_prev_ref = &mut *partition_prev;
                let new_node = run.take().unwrap();
                let mut new_node_mut = new_node.borrow_mut();
                new_node_mut.next = partition_prev_ref.next.take();
                partition_prev_ref.next = Some(new_node.clone());
                drop(new_node_mut);

                partition_prev = &mut new_node.borrow_mut() as *mut _;
                run = &mut current;
            }
        } else {
            // Move forward
            prev = current as *mut Box<ListNode>;
            current = &mut node.borrow_mut().next;
            run = current;
        }
    }

    dummy_ref.next
}

// Helper function to create a linked list from a vector
fn create_linked_list(values: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if values.is_empty() {
        return None;
    }
    let mut head = ListNode::new(values[0]);
    let mut current = &mut head;
    for val in &values[1..] {
        let new_node = ListNode::new(*val);
        current.next = Some(Rc::new(RefCell::new(new_node)));
        current = &mut current.next.as_mut().unwrap().borrow_mut();
    }
    Some(Rc::new(RefCell::new(head)))
}

// Helper function to convert linked list to vector for easy testing
fn linked_list_to_vec(node: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = node;
    while let Some(node) = current {
        result.push(node.borrow().val);
        current = node.borrow_mut().next.take();
    }
    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_partition_list() {
        let head = create_linked_list(vec![1, 4, 3, 2, 5, 2]);
        let result = partition(head, 3);
        assert_eq!(linked_list_to_vec(result), vec![1, 2, 2, 4, 3, 5]);

        let head = create_linked_list(vec![2, 1]);
        let result = partition(head, 2);
        assert_eq!(linked_list_to_vec(result), vec![1, 2]);

        let head = create_linked_list(vec![5, 3, 1, 4, 2]);
        let result = partition(head, 3);
        assert_eq!(linked_list_to_vec(result), vec![1, 2, 5, 3, 4]);
    }
}

fn main() {
    let head = create_linked_list(vec![1, 4, 3, 2, 5, 2]);
    let result = partition(head, 3);
    println!("{:?}", linked_list_to_vec(result));  // [1, 2, 2, 4, 3, 5]

    let head = create_linked_list(vec![2, 1]);
    let result = partition(head, 2);
    println!("{:?}", linked_list_to_vec(result));  // [1, 2]

    let head = create_linked_list(vec![5, 3, 1, 4, 2]);
    let result = partition(head, 3);
    println!("{:?}", linked_list_to_vec(result));  // [1, 2, 5, 3, 4]
}

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

// Partition linked list into two groups: values < x and values >= x.
// Rearranges nodes in a single pass without creating separate lists.
//
// Time Complexity: O(n) where n is the number of nodes
// Space Complexity: O(1) excluding the output list
func partitionListSingleRearrange(head *ListNode, x int) *ListNode {
  // Create a dummy node to simplify edge cases
  dummy := &ListNode{Val: 0}
  dummy.Next = head

  // Find the node just before the partition point
  prev := dummy
  current := head

  for current != nil && current.Val < x {
    prev = current
    current = current.Next
  }

  // Now prev is the last node with value < x (or dummy if all nodes >= x)
  // current is the first node with value >= x (or nil if all nodes < x)

  // If all nodes are less than x or list is empty, return as is
  if current == nil {
    return dummy.Next
  }

  // Now we need to insert nodes with value < x before the partition point
  partitionPrev := prev  // Last node of < x group
  run := current         // Start from the partition point

  for run != nil {
    if run.Val < x {
      // Remove run from its position
      current.Next = run.Next

      // Insert run before the partition point
      run.Next = partitionPrev.Next
      partitionPrev.Next = run

      // Move partitionPrev forward
      partitionPrev = run

      // Current stays the same to check the next node
      run = current.Next
    } else {
      // Move forward
      current = run
      run = run.Next
    }
  }

  return dummy.Next
}

// Helper function to create a linked list from a slice
func createLinkedList(values []int) *ListNode {
  if len(values) == 0 {
    return nil
  }
  head := &ListNode{Val: values[0]}
  current := head
  for i := 1; i < len(values); i++ {
    current.Next = &ListNode{Val: values[i]}
    current = current.Next
  }
  return head
}

// Helper function to convert linked list to slice for easy testing
func linkedListToSlice(node *ListNode) []int {
  result := []int{}
  for node != nil {
    result = append(result, node.Val)
    node = node.Next
  }
  return result
}

// Test cases
func main() {
  head := createLinkedList([]int{1, 4, 3, 2, 5, 2})
  result := partitionListSingleRearrange(head, 3)
  fmt.Println(linkedListToSlice(result))  // [1 2 2 4 3 5]

  head = createLinkedList([]int{2, 1})
  result = partitionListSingleRearrange(head, 2)
  fmt.Println(linkedListToSlice(result))  // [1 2]

  head = createLinkedList([]int{5, 3, 1, 4, 2})
  result = partitionListSingleRearrange(head, 3)
  fmt.Println(linkedListToSlice(result))  // [1 2 5 3 4]
}

Common mistakes

Edge cases to handle

Case	Behavior	Example
Empty list	Return null	`[]` → `[]`
All nodes < x	Larger list is null	`[1, 2]` with x=5 → `[1, 2]`
All nodes >= x	Smaller list is null	`[5, 6]` with x=3 → `[5, 6]`
x is minimum	All nodes >= x	`[1, 2, 3]` with x=-1 → `[1, 2, 3]`
x is maximum	All nodes < x	`[1, 2, 3]` with x=100 → `[1, 2, 3]`
Single node	Partition trivially	`[5]` with x=3 → `[5]`
Equal values	Preserve order	`[3, 3, 3]` with x=3 → `[3, 3, 3]` (all >= x)
Negative values	Treat as regular integers	`[-1, 2, -3]` with x=0 → `[-1, -3, 2]`

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

"""
Solution for Partition List
"""

def solve():
    """Implementation for approach 3 of Partition List"""
    pass

if __name__ == "__main__":
    print("Solution ready")

#include <bits/stdc++.h>
using namespace std;

// Solution for Partition List
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

/**
 * Solution for Partition List
 * Approach 3
 */
public class PartitionListOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

/**
 * Solution for Partition List
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

/// Solution for Partition List
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

package main

import "fmt"

// Solution for Partition List
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Interview Tips

Why partition instead of sort? The problem explicitly wants to preserve relative order, not sort. Sorting would be O(n log n) with more memory overhead.
Why dummy nodes? They eliminate special cases when dealing with the head of the result list. Instead of checking if the head is null, you always append to dummy.next.
Two-head vs. single-rearrange: The two-head approach is clearer and less error-prone. Use it in interviews unless asked explicitly for a space-optimal solution.
Handling the partition boundary: Be precise about comparison operators. The problem says “less than x” (strictly). Values equal to x go to the right group.
Why not create new nodes? You must reuse existing nodes and only rearrange pointers. Creating new nodes would waste space and miss the point of the problem.
Follow-up — Partition around three-way: Extend this to partition into three groups (< x, == x, > x), which is useful for three-way quicksort or the Dutch National Flag problem.

Partition List

Problem Statement

Examples

Constraints

Real-World Applications

Complexity Comparison

Which approach should you learn first?

Approach 1: Two List Heads (Recommended)

Step-by-step Example

Pseudocode

Solution Code

Approach 2: Single List Rearrange

Step-by-step Example

Pseudocode

Solution Code

Common mistakes

Edge cases to handle

Approach 3: Optimized Two-Pointer

Pseudocode

Solution Code

Related Problems

Interview Tips