Partition List

Updated on 02 July, 2025
Partition List header image

Problem Statement

When provided with a linked list and a value x, the task is to rearrange the nodes in such a way that all nodes with values less than x appear before any node with a value greater than or equal to x in the list. During this rearrangement, it's critical to maintain the original relative order of the nodes that fall into these two categories (less than x and greater than or equal to x). Essentially, it involves segregating the linked list into two parts based on the criteria defined by x, while ensuring that the order of elements within these segregated parts remains unchanged.

Examples

Example 1

Input:

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

Output:

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

Example 2

Input:

head = [2,1], x = 2

Output:

[1,2]

Constraints

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

Approach and Intuition

Given the nature of the problem, the intuitive approach is to effectively manage two sub-lists and then concatenate them:

  1. Initialize Two Placeholder Nodes: Create two new linked list heads, one for elements less than x (let’s call it lessHead) and another for elements greater than or equal to x (greaterHead). These will act as starting points to build the two sub-lists.

  2. Iterate Through the Original List: Traverse the original linked list node by node.

    • If a node’s value is less than x, append it to the lessHead list.
    • If a node’s value is greater than or equal to x, append it to the greaterHead list.
  3. Maintain Order Within Sub-lists: It’s important to add the current node to the end of the respective sub-lists to preserve the relative order of nodes. This can be managed by maintaining a pointer to the tail of both lessHead and greaterHead, updating it each time a new node is added.

  4. Merge the Two Sub-lists: After the original list has been completely traversed, connect the end of the lessHead sub-list to the start of the greaterHead sub-list.

  5. Consider Edge Cases: The algorithm should handle cases with empty lists, lists where all elements are the same, and lists where all elements are already partitioned correctly. This ensures that the result always adheres to the constraints and conditions provided.

By following this approach, the linked list is efficiently partitioned, guaranteeing that nodes less than x are positioned before nodes greater than or equal to x, while their original relative order is preserved. This technique leverages direct linkage manipulations which are optimal for operations in linked lists, avoiding unnecessary use of additional space or complex data structures.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    ListNode* separate(ListNode* node, int pivot) {
        ListNode* less_head = new ListNode(0);
        ListNode* less_tail = less_head;
        ListNode* greater_head = new ListNode(0);
        ListNode* greater_tail = greater_head;
        while (node != NULL) {
            if (node->val < pivot) {
                less_tail->next = node;
                less_tail = less_tail->next;
            } else {
                greater_tail->next = node;
                greater_tail = greater_tail->next;
            }
            node = node->next;
        }
        greater_tail->next = NULL;
        less_tail->next = greater_head->next;
        return less_head->next;
    }
};

The provided C++ solution defines a method named separate inside a Solution class, which aims to partition a linked list around a given pivot value. The method accepts a pointer to the head of the list (ListNode* node) and an integer (pivot) representing the pivot value. The list nodes with values less than the pivot are moved to one linked list, and those with values greater or equal are moved to another.

To achieve this partition:

  • Initialize two dummy head nodes, less_head and greater_head, to simplify node connection without handling special cases for the head node.
  • Use two pointers, less_tail and greater_tail, to maintain the ends of the two growing lists (less than pivot and greater/equal to pivot).

During iteration through the input list:

  • Nodes with values less than the pivot are appended to the list headed by less_head.
  • Nodes with values greater or equal to the pivot are appended to the list headed by greater_head.
  • At the end of the iteration, ensure the list headed by greater_tail is properly terminated with a NULL to signify the end of the list.

Finally:

  • Connect the list containing nodes less than the pivot to the list of nodes greater than or equal to the pivot.
  • Return the head of the modified list, which effectively omits the initial dummy node (less_head->next).

This method efficiently partitions the linked list in one pass, using constant space for pointers and ensuring that nodes are rearranged without creating new ones, just re-linking the existing nodes according to their values relative to the pivot.

java
class Solution {
    public ListNode split(ListNode start, int pivot) {
        ListNode lowHead = new ListNode(0);
        ListNode lowTail = lowHead;
        ListNode highHead = new ListNode(0);
        ListNode highTail = highHead;
    
        while (start != null) {
            if (start.val < pivot) {
                lowTail.next = start;
                lowTail = lowTail.next;
            } else {
                highTail.next = start;
                highTail = highTail.next;
            }
    
            start = start.next;
        }
    
        highTail.next = null;
        lowTail.next = highHead.next;
        return lowHead.next;
    }
}

This Java solution addresses the problem of partitioning a linked list around a given pivot value, such that all nodes less than the pivot come before all nodes greater than or equal to the pivot. The function split is defined to handle this logic and takes two parameters: the head of the list (start) and the pivot value (pivot).

Here's how the solution operates:

  1. Two dummy nodes, lowHead and highHead, are created to form the beginning of two separate linked lists: one for values lower than the pivot and another for values higher or equal.
  2. Two pointers, lowTail and highTail, start at these dummy nodes and help in building the two lists.
  3. As you iterate through the original list, each node is either added to the end of the lowTail list (if its value is less than the pivot) or to the highTail list (if its value is greater than or equal).
  4. This iteration continues until all elements of the original list are examined.
  5. The list of higher or equal values must have its last node pointing to null to denote the end of the list.
  6. To merge the two lists, set the next pointer of the lowTail (end of lower value list) to the head of the higher values list, which starts right after the dummy node highHead.
  7. Finally, return the head of the modified list, which is now properly partitioned, by pointing to the next of lowHead.

This method effectively re-arranges the nodes of the original list without needing additional memory for new nodes, thereby providing an efficient in-place solution.

c
struct ListNode* separate(struct ListNode* start, int threshold) {
    struct ListNode* less_than_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    less_than_head->next = NULL;
    struct ListNode* less = less_than_head;
    struct ListNode* greater_than_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    greater_than_head->next = NULL;
    struct ListNode* greater = greater_than_head;
        
    while (start != NULL) {
        if (start->val < threshold) {
            less->next = start;
            less = less->next;
        } else {
            greater->next = start;
            greater = greater->next;
        }
        start = start->next;
    }
    greater->next = NULL;
    less->next = greater_than_head->next;
    return less_than_head->next;
}

The given C language code defines a function separate that partitions a linked list based on a threshold value. The function accepts a linked list (start) and an integer (threshold) as parameters. The goal is to rearrange the linked list so that all nodes with values less than the threshold are moved before nodes with values equal to or greater than the threshold.

  • The function initializes two dummy head nodes: less_than_head for the list of elements less than the threshold and greater_than_head for the list of elements equal to or greater than the threshold.
  • It iterates through the input list, and segregates nodes into the less and greater lists based on their values compared to the threshold.
  • After the iteration, ensure that the last node in the greater list points to NULL to mark the end of that list.
  • The next of the last less node points to the first element of the greater_than_head list to concatenate the two lists.
  • Finally, return the next of the less_than_head which is effectively the head of the newly arranged linked list.

This rearrangement is done in-place, and the algorithm efficiently partitions the nodes with a single traversal through the original list. The approach ensures that the relative order of nodes in each partition is preserved and it uses constant space for the pointers, excluding the input list nodes themselves.

js
var splitList = function (node, pivot) {
    var lowStart = new ListNode(0);
    var lowEnd = lowStart;
    var highStart = new ListNode(0);
    var highEnd = highStart;
    while (node != null) {
        if (node.val < pivot) {
            lowEnd.next = node;
            lowEnd = lowEnd.next;
        } else {
            highEnd.next = node;
            highEnd = highEnd.next;
        }
        node = node.next;
    }
    highEnd.next = null;
    lowEnd.next = highStart.next;
    return lowStart.next;
};

The JavaScript function "splitList" is designed to partition a linked list around a pivot value. It rearranges the list so that all nodes with values less than the pivot come before nodes with values greater than or equal to the pivot. Here's a breakdown of how it accomplishes this:

  • Initialize two dummy nodes, lowStart and highStart, which act as the starting points for the two parts of the split list.
  • Utilize two pointers, lowEnd and highEnd, which help in appending nodes to the respective parts.
  • Traverse through the linked list using a while loop. During each iteration, compare the current node's value with the pivot:
    • If the node's value is less than the pivot, append it to the lowEnd.
    • Otherwise, append it to the highEnd.
  • After exiting the loop, set the next pointer of highEnd to null to mark the end of the high part of the list.
  • Connect the end of the low part list to the beginning of the high part list.
  • Return the next node of lowStart as it points to the head of the newly arranged list.

This method effectively partitions the list with a time complexity of O(n) and does not require additional space beyond the few temporary pointers, making it space efficient.

python
class Solution(object):
    def rearrangeNodes(self, start: ListNode, pivot: int) -> ListNode:
        # Initialize two list heads and current pointers
        lower = lower_head = ListNode(0)
        higher = higher_head = ListNode(0)
    
        while start:
            # Distribute nodes into lower or higher based on their value
            if start.val < pivot:
                lower.next = start
                lower = lower.next
            else:
                higher.next = start
                higher = higher.next
    
            # Proceed to next node in original list
            start = start.next
    
        # Terminate the higher value list
        higher.next = None
        # Connect lower values list to higher values list
        lower.next = higher_head.next
    
        return lower_head.next

The provided Python code defines a function that partitions a linked list around a given pivot value. Each node in the linked list has a numeric value, and the function rearranges the nodes such that all nodes with values less than the pivot are moved before nodes with values greater than or equal to the pivot. The rearrangement is performed using the following steps:

  • Initialize two dummy head nodes, lower_head and higher_head, to help in segregating nodes into two lists: one for values lower than the pivot and one for values higher or equal.
  • Traverse through the original list. Depending on whether the node's value is less than the pivot, append it to the end of the lower list, or otherwise to the higher list.
  • Properly manage the next pointers. After evaluating a node, proceed to the next node in the list.
  • Ensure that the higher list is terminated properly to avoid any potential cyclic linking in the list.
  • Connect the lower list to the higher list by setting the next pointer of the last node of the lower list to the first node of the higher list.
  • Return the next node of lower_head as the new head of the rearranged list, excluding the dummy head.

This solution efficiently partitions the list with a single traversal, resulting in a time complexity of O(n), where n is the number of nodes in the list, and it uses O(1) extra space since no additional nodes are created, only pointers are reassigned.

Comments

No comments yet.