Leetcode - 86. Partition List

🔍 Approach

To solve this cleanly, we use the two-pointer technique:

1. Create two dummy nodes:

   • One (ldummy) for values less than x
   • One (gdummy) for values greater than or equal to x

2. Traverse the original list:

   • Add nodes with value < x to the "less than" list.
   • Add others to the "greater or equal" list.

3. Connect the two lists together at the end.

4. Return the start of the combined list.

This method ensures we preserve the relative order of nodes while separating them based on the given value x.

---

✅ Code Implementation

/**
 * 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 ldummy = new ListNode(0, null); // dummy head for < x
    let gdummy = new ListNode(0, null); // dummy head for >= x
    let ltrav = ldummy;
    let gtrav = gdummy;
    let trav = head;

    while (trav) {
        if (trav.val < x) {
            ltrav.next = trav;
            ltrav = ltrav.next;
        } else {
            gtrav.next = trav;
            gtrav = gtrav.next;
        }
        trav = trav.next;
    }

    gtrav.next = null;          // end of greater list
    ltrav.next = gdummy.next;   // connect two lists
    return ldummy.next;         // head of the final list
};

---

⏱️ Time and Space Complexity

• Time Complexity: O(n)
  
  We visit each node exactly once during traversal.

• Space Complexity: O(1)
  
  No extra space used except a few pointers (constant space), as we rearrange in-place.

---

📌 Example

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

Step-by-step partition:
< x list: [1 -> 2 -> 2]
>= x list: [4 -> 3 -> 5]

Final result: [1 -> 2 -> 2 -> 4 -> 3 -> 5]

---

🧩 Final Thoughts

This pattern of splitting and merging with dummy nodes is a great way to simplify many linked list problems. Once you get used to it, you’ll find similar applications in merging, sorting, and reordering linked lists.

---