Partition List

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

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;
    }
};