Problem Description

The "Partition List" problem asks you to rearrange a singly linked list based on a given value x. Specifically, you are given the head of a singly linked list and an integer x. You must partition the list so that all nodes with values less than x come before nodes with values greater than or equal to x.

Importantly, you must preserve the original relative order of the nodes in each of the two partitions. The list should be rearranged by re-linking the nodes, not by creating new ones (i.e., do not reuse or copy nodes; only rearrange the existing nodes).

• You must return the head of the new partitioned list.
• There is always at least one valid solution.
• Do not create new list nodes; just change the links between nodes.

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

Thought Process

To solve this problem, the first idea might be to scan the list and, for each node, decide if it should go before or after the partition value x. A naive approach could involve creating two arrays or lists: one for nodes less than x and one for nodes greater than or equal to x, then combining them. However, this would require extra space and possibly copying nodes, which is not allowed.

Instead, since we must not create new nodes and must maintain relative order, we need to work directly with the node links. A good analogy is to imagine sorting a deck of cards into two piles (less than x and greater than or equal to x), but always keeping the order of cards within each pile. Once sorted, we can connect the two piles together.

The challenge is to do this efficiently, in one pass, and without breaking the list or losing any nodes.

Solution Approach

The optimal solution uses two pointers (or dummy nodes) to build two separate linked lists: one for nodes less than x ("before" list), and one for nodes greater than or equal to x ("after" list). We traverse the original list once, appending each node to the appropriate list. At the end, we connect the "before" list to the "after" list.

1. Initialize two dummy nodes: One for the "before" list and one for the "after" list. These help simplify edge cases, such as when all nodes are less than or greater than x.
2. Use two tail pointers: before and after start at the dummy nodes. As we traverse the original list, we append each node to the correct list and move the respective tail.
3. Traverse the original list: For each node, check if its value is less than x. If so, append it to the "before" list; otherwise, append it to the "after" list.
4. Connect the lists: After traversing, connect the end of the "before" list to the start of the "after" list (skipping its dummy head). Set the end of the "after" list to null to terminate the list.
5. Return the new head: The new head is the node after the "before" dummy node.

This approach preserves the order of nodes within each partition and does not create or copy nodes, only relinks them.

Example Walkthrough

Let's walk through an example with head = [1, 4, 3, 2, 5, 2] and x = 3:

1. Initialize: Two dummy nodes: before_head and after_head. Two pointers: before and after.
2. Traverse:
   • Node 1: 1 < 3 → append to "before" list.
   • Node 4: 4 ≥ 3 → append to "after" list.
   • Node 3: 3 ≥ 3 → append to "after" list.
   • Node 2: 2 < 3 → append to "before" list.
   • Node 5: 5 ≥ 3 → append to "after" list.
   • Node 2: 2 < 3 → append to "before" list.
3. Connect: Link the end of the "before" list to the start of the "after" list. Set the end of the "after" list to null.
4. Result: The final list is [1, 2, 2, 4, 3, 5].

At each step, the order of nodes in each partition is preserved.

Time and Space Complexity

Brute-force Approach: If we used extra arrays or lists, the time complexity would still be O(n), but space complexity would be O(n) due to the extra data structures and possibly node copying (which is not allowed).

Optimized Approach: The solution above:

• Time Complexity: O(n), where n is the number of nodes, because we traverse the list once.
• Space Complexity: O(1), because we only use a fixed number of pointers and do not allocate space proportional to the input size. We only rearrange the existing nodes.

Summary

The "Partition List" problem is efficiently solved by using two dummy nodes to create two partitions and then linking them together. This approach is elegant because it:

• Preserves the relative order of nodes within each partition.
• Requires only a single pass through the list.
• Does not require extra space for new nodes or arrays.
• Uses simple pointer manipulation to achieve the desired result.

Code Implementation

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

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        before_head = ListNode(0)
        after_head = ListNode(0)
        before = before_head
        after = after_head

        current = head
        while current:
            if current.val < x:
                before.next = current
                before = before.next
            else:
                after.next = current
                after = after.next
            current = current.next

        after.next = None
        before.next = after_head.next
        return before_head.next
      

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode before_head(0), after_head(0);
        ListNode* before = &before_head;
        ListNode* after = &after_head;
        ListNode* current = head;
        while (current) {
            if (current->val < x) {
                before->next = current;
                before = before->next;
            } else {
                after->next = current;
                after = after->next;
            }
            current = current->next;
        }
        after->next = nullptr;
        before->next = after_head.next;
        return before_head.next;
    }
};
      

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode before_head = new ListNode(0);
        ListNode after_head = new ListNode(0);
        ListNode before = before_head;
        ListNode after = after_head;
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                before.next = current;
                before = before.next;
            } else {
                after.next = current;
                after = after.next;
            }
            current = current.next;
        }
        after.next = null;
        before.next = after_head.next;
        return before_head.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    let before_head = new ListNode(0);
    let after_head = new ListNode(0);
    let before = before_head;
    let after = after_head;
    let current = head;
    while (current) {
        if (current.val < x) {
            before.next = current;
            before = before.next;
        } else {
            after.next = current;
            after = after.next;
        }
        current = current.next;
    }
    after.next = null;
    before.next = after_head.next;
    return before_head.next;
};