Partition List Around Value X

📋

Problem

Imagine you have a queue of people waiting, and you want to rearrange them so that everyone shorter than a certain height stands in front, preserving their relative order.

Given the head of a singly linked list and a value x, partition the list so that all nodes less than x come before nodes greater than or equal to x. The original relative order of the nodes in each partition should be preserved. Return the head of the modified list.

1 ≤ n ≤ 10^5 (number of nodes in the list)-10^6 ≤ Node.val, x ≤ 10^6

Edge cases: All nodes less than x → list remains unchangedAll nodes greater or equal to x → list remains unchangedList with only one node → output is the same node

</>

IDE

def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:public ListNode partition(ListNode head, int x)ListNode* partition(ListNode* head, int x)function partition(head, x)

def partition(head, x):
    # Write your solution here
    pass

class Solution {
    public ListNode partition(ListNode head, int x) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* partition(ListNode* head, int x) {
    // Write your solution here
    return nullptr;
}

function partition(head, x) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [4,3,5,1,2,2]Incorrectly placing nodes greater or equal to x before nodes less than x, violating partition order.✅ Use two dummy heads to build separate lists for nodes < x and nodes >= x, then concatenate less list before greater or equal list.

Wrong: [1,4,3,2,5,2]Returning original list without partitioning or failing to reorder nodes.✅ Implement partition logic that separates nodes based on value and preserves relative order.

Wrong: [5]Crashing or returning incorrect output on single node input due to null pointer or edge case mishandling.✅ Check for null or single node input and return head as is without modification.

Wrong: [3,3,3]Incorrectly moving nodes equal to x into less than partition or losing order.✅ Ensure nodes with val >= x are appended to the second list without reordering.

Wrong: Timeout or no outputUsing nested loops or multiple passes causing O(n^2) complexity.✅ Use a single pass with two dummy heads to achieve O(n) time complexity.

✓

Test Cases

Focus on handling boundary cases like empty or single-node lists to solidify your base cases.

Watch out for subtle bugs in partition logic; test with tricky inputs that expose greedy or order mistakes.

Optimize your solution to run in linear time and constant space to handle large inputs efficiently.

t1_01basic

Input{"head":[1,4,3,2,5,2],"x":3}

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

⏱ Performance - must finish in 2000ms

Nodes less than 3 are 1,2,2 and appear before nodes greater or equal to 3 (4,3,5), preserving original relative order.

💡 Think about splitting the list into two parts: nodes less than x and nodes greater or equal to x.

💡 Use two dummy heads to build two separate lists and then connect them.

💡 After building two lists, link the less list's tail to the greater or equal list's head.

Why it failed: Output order incorrect or nodes misplaced. Likely failed to preserve relative order or incorrectly merged lists. Fix by using two dummy heads and appending nodes in original order.

✓ Correct partition preserving relative order with two dummy heads.

t1_02basic

Input{"head":[2,1],"x":2}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Node 1 is less than 2 and appears before node 2 which is equal to 2, preserving order.

💡 Check how nodes less than x are placed before nodes greater or equal to x.

💡 Maintain two separate lists and concatenate them at the end.

💡 Ensure the last node of the greater or equal list points to null.

Why it failed: Failed to reorder nodes correctly or did not terminate the list properly. Fix by ensuring the greater or equal list ends with null and concatenation is correct.

✓ Correctly partitions small list preserving order.

t2_01edge

Input{"head":[],"x":1}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input should return empty list.

💡 Consider what happens when the input list is empty.

💡 Your code should handle null or empty head gracefully.

💡 Return the head as is if it's null.

Why it failed: Code crashes or returns non-empty list on empty input. Fix by checking if head is null and returning it immediately.

✓ Handles empty list input correctly.

t2_02edge

Input{"head":[5],"x":3}

Expected[5]

⏱ Performance - must finish in 2000ms

Single node list remains unchanged regardless of x.

💡 Test with only one node in the list.

💡 Partitioning a single node should return the same node.

💡 Ensure no unnecessary changes or errors occur with single node.

Why it failed: Code alters single node list incorrectly or crashes. Fix by handling single node case without modification.

✓ Correctly handles single node list.

t2_03edge

Input{"head":[3,3,3],"x":3}

Expected[3,3,3]

⏱ Performance - must finish in 2000ms

All nodes equal to x remain in original order.

💡 Check behavior when all nodes are equal to x.

💡 Nodes equal to x should be in the greater or equal partition.

💡 Ensure original order is preserved and no nodes are lost.

Why it failed: Code incorrectly moves or removes nodes equal to x. Fix by including nodes with val >= x in the second list without reordering.

✓ Correctly partitions list with all nodes equal to x.

t3_01corner

Input{"head":[1,4,2,10,2,5,3],"x":3}

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

⏱ Performance - must finish in 2000ms

Nodes less than 3 (1,2,2) appear before nodes >= 3 (4,10,5,3), preserving order.

💡 Beware of greedy approaches that move nodes incorrectly.

💡 Check that nodes are appended in original order within partitions.

💡 Use two dummy heads and append nodes as you traverse.

Why it failed: Greedy approach failed: nodes reordered incorrectly or some nodes misplaced. Fix by using two separate lists and concatenating after traversal.

✓ Correctly partitions list avoiding greedy trap.

t3_02corner

Input{"head":[3,1,2,3,4],"x":3}

Expected[1,2,3,3,4]

⏱ Performance - must finish in 2000ms

Nodes less than 3 (1,2) appear before nodes >= 3 (3,3,4), preserving order.

💡 Check that nodes equal to x are included in the greater or equal partition.

💡 Do not mix nodes less than x with nodes equal to x.

💡 Ensure the concatenation order is less list followed by greater or equal list.

Why it failed: Confused nodes equal to x with less than x, causing wrong order. Fix by strictly separating nodes < x and >= x.

✓ Correctly handles nodes equal to x in partition.

t3_03corner

Input{"head":[2,2,2,2,2],"x":2}

Expected[2,2,2,2,2]

⏱ Performance - must finish in 2000ms

All nodes equal to x remain in original order in the greater or equal partition.

💡 Check that nodes equal to x are not mistakenly placed in less than partition.

💡 Verify that the relative order of nodes equal to x is preserved.

💡 Use two dummy heads and append nodes accordingly.

Why it failed: Incorrectly placing nodes equal to x in less partition or losing order. Fix by appending nodes with val >= x to the second list.

✓ Correctly partitions list with all nodes equal to x.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n) time complexity; solution must complete within 2 seconds.

💡 Aim for O(n) time complexity by traversing the list once.

💡 Avoid nested loops or repeated traversals.

💡 Use two dummy heads and link lists in one pass.

Why it failed: Solution exceeds time limit due to higher than O(n) complexity. Fix by implementing single pass partition with two dummy heads.

✓ Solution runs efficiently in O(n) time.

Practice

1. Consider the following Python code implementing an optimal linked list. After executing these operations: addAtHead(1), addAtTail(3), addAtIndex(1, 2), what is the value returned by get(1)?

easy

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Trace addAtHead(1)

   List: dummy -> 1; size=1; tail points to node with val=1.

2. Step 2: Trace addAtTail(3)

   List: dummy -> 1 -> 3; size=2; tail points to node with val=3.

3. Step 3: Trace addAtIndex(1, 2)

   Insert 2 at index 1: dummy -> 1 -> 2 -> 3; size=3; tail remains at 3.

4. Step 4: Trace get(1)

   Index 1 corresponds to node with val=2.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Inserted 2 at index 1 correctly; get(1) returns 2 [OK]

Hint: Indexing starts after dummy node; careful with traversal loops [OK]

Common Mistakes:

• Off-by-one in traversal loop
• Not updating tail on addAtIndex at end
• Returning wrong node value

2. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list

3. Identify the bug in the following code snippet for splitting a linked list into k parts:

medium

A. Line where curr is advanced without checking if curr is None, causing AttributeError.

B. Line where tails[i].next is set to curr without checking if curr is None.

C. Line where tails[i].next is set to None, which breaks the list prematurely.

D. Line where dummy_heads are created, which wastes extra space.

Solution

1. Step 1: Analyze pointer advancement

   Inside the inner loop, curr is advanced with curr = curr.next without checking if curr is None.

2. Step 2: Identify potential error

   If curr is None, accessing curr.next raises AttributeError. The check must happen before advancing curr.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing None check before curr = curr.next causes runtime error [OK]

Hint: Always check curr is not None before accessing curr.next [OK]

Common Mistakes:

• Forgetting None check before pointer advance
• Incorrectly cutting list by setting next to None too early
• Misusing dummy heads

4. Suppose the linked list with random pointers can contain cycles formed by next pointers (i.e., the list is not necessarily acyclic). Which modification to the optimal weaving approach is necessary to correctly copy such a list?

hard

A. Use a hash map to track visited nodes to avoid infinite loops during traversal.

B. Modify the separation step to break cycles before copying nodes.

C. No modification needed; the weaving approach works as is for cyclic lists.

D. Use recursion with memoization to handle cycles safely.

Solution

1. Step 1: Understand cycle impact on weaving approach

   The weaving approach assumes linear traversal; cycles cause infinite loops.

2. Step 2: Identify necessary modification

   Tracking visited nodes with a hash map prevents infinite loops by stopping revisits.

3. Step 3: Evaluate other options

   Breaking cycles before copying is complex; recursion risks stack overflow; no modification leads to infinite loop.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map prevents infinite traversal in cyclic lists [OK]

Hint: Cycles require visited tracking to avoid infinite loops [OK]

Common Mistakes:

• Assuming acyclic list always
• Trying to break cycles before copying
• Using recursion without cycle detection

5. Suppose the problem is modified so that nodes can be reused multiple times (i.e., after reversing a group, nodes can appear again in subsequent groups). Which of the following changes to the algorithm correctly handles this scenario?

hard

A. Modify the algorithm to create new nodes for each group reversal to avoid modifying original nodes in place.

B. This problem cannot be solved by reversal; instead, use a queue to simulate repeated node usage.

C. Use recursion with memoization to store reversed groups and reuse them without modifying the original list.

D. Use the same iterative reversal approach but reset pointers to allow reusing nodes in multiple groups.

Solution

1. Step 1: Understand node reuse implication

   Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.

2. Step 2: Evaluate algorithm modifications

   In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.

3. Step 3: Assess other options

   Resetting pointers (A) breaks list integrity; recursion with memoization (C) is complex and not standard; queue simulation (B) does not solve reversal reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Duplicating nodes preserves original list for reuse [OK]

Hint: Node reuse requires duplication, not in-place reversal [OK]

Common Mistakes:

• Trying to reuse nodes in place
• Ignoring list integrity
• Assuming recursion memoization solves reuse