Partition List

How it works

Instead of storing values in arrays, we can build two separate linked lists as we traverse: one for nodes less than x, one for nodes greater than or equal to x. Using dummy head nodes simplifies edge case handling.

At the end, we connect the tail of the "less" list to the head of the "greater" list, and terminate the "greater" list to avoid cycles. This achieves O(1) extra space by reusing the original nodes.

Steps

1. Create two dummy nodes as heads for the "left" (less than x) and "right" (greater or equal) lists.
2. Maintain tail pointers for both lists.
3. Traverse the original list:
   • If the current node's value is less than x, append it to the left list.
   • Otherwise, append it to the right list.
4. Connect the left list's tail to the right list's first real node (skip dummy).
5. Set the right list's tail's next to null to terminate the list.
6. Return the first real node of the left list.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting to Terminate the Right List

After connecting the left list to the right list, you must set rtail.next = null. Without this, the last node of the right list may still point to a node in the left list from the original structure, creating a cycle and causing infinite loops.

Using Strict Greater Than Instead of Greater or Equal

The partition condition requires nodes with values less than x to come first, and nodes greater than or equal to x to come second. Using > instead of >= for the right partition will incorrectly place nodes equal to x in the left partition.

Not Using Dummy Nodes

Trying to handle the head of each partition manually without dummy nodes leads to complex edge case handling. Using dummy nodes (left and right) as placeholders simplifies the code and eliminates null checks when the first node is encountered for each partition.

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        left, right = ListNode(), ListNode()
        ltail, rtail = left, right

        while head:
            if head.val < x:
                ltail.next = head
                ltail = ltail.next
            else:
                rtail.next = head
                rtail = rtail.next
            head = head.next

        ltail.next = right.next
        rtail.next = None
        return left.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 leftDummy(0), rightDummy(0);
        ListNode *ltail = &leftDummy, *rtail = &rightDummy;

        while (head) {
            if (head->val < x) {
                ltail->next = head;
                ltail = ltail->next;
            } else {
                rtail->next = head;
                rtail = rtail->next;
            }
            head = head->next;
        }

        ltail->next = rightDummy.next;
        rtail->next = nullptr;
        return leftDummy.next;
    }
};