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. Given the following code for odd-even linked list rearrangement, what is the output list after running the function on the input list [1, 2, 3, 4]?

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

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
    res.append(curr.val)
    curr = curr.next
print(res)

easy

A. [1, 2, 3, 4]

B. [1, 3, 2, 4]

C. [2, 4, 1, 3]

D. [1, 3, 4, 2]

Solution

1. Step 1: Trace first iteration of while loop

   odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.

2. Step 2: Loop ends as even.next is null; link odd.next to even_head (2)

   Final list order: 1 -> 3 -> 2 -> 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]

Hint: Odd nodes first, then even nodes in original order [OK]

Common Mistakes:

• Confusing node values with indices
• Off-by-one errors in pointer updates

2. What is the amortized time complexity of the visit, back, and forward operations in the two stacks approach for browser history, assuming n total operations?

medium

A. O(1) amortized per operation since each URL is pushed and popped at most once per stack

B. O(n) total for all operations combined, but O(1) worst-case per operation

C. O(log n) per operation due to stack resizing costs

D. O(n) per operation because each visit may clear the forward stack

Solution

1. Step 1: Analyze push/pop operations per URL

   Each URL is pushed once onto back_stack and popped at most once to forward_stack, and vice versa.

2. Step 2: Calculate amortized cost

   Since each URL moves between stacks a limited number of times, total operations over n steps average to O(1) per operation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) is standard for two stacks navigation [OK]

Hint: Each URL moves between stacks only a few times [OK]

Common Mistakes:

• Assuming clearing forward stack is O(n) per visit
• Confusing amortized with worst-case
• Ignoring stack push/pop costs

3. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?

medium

A. O(n) -- recursion stack uses space proportional to list length

B. O(1) -- only constant extra pointers used

C. O(log n) -- recursion depth is halved each call

D. O(n^2) -- due to repeated pointer updates in recursion

Solution

1. Step 1: Identify recursion depth

   The helper function recurses once per node, so recursion depth is n.

2. Step 2: Calculate space usage

   Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack proportional to list length [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming constant space due to in-place changes
• Confusing recursion depth with log n
• Overestimating to quadratic space

4. 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

5. Suppose the linked list design is extended to allow negative indices in get and addAtIndex operations, where -1 refers to the last element, -2 to the second last, and so forth. Which modification correctly supports this feature without degrading average operation time complexity?

hard

A. Reject negative indices as invalid to keep implementation simple and efficient.

B. Traverse from tail backwards for negative indices to achieve O(1) access.

C. Use a doubly linked list instead of singly linked list to support backward traversal efficiently.

D. Modify get and addAtIndex to convert negative indices to positive by adding size, then proceed normally.

Solution

1. Step 1: Understand negative index semantics

   Negative indices map to positive indices by adding the list size (e.g., -1 -> size-1).

2. Step 2: Implement index normalization

   Convert negative indices to positive by adding size before performing normal operations, preserving O(n) traversal.

3. Step 3: Evaluate alternatives

   Backward traversal from tail is not possible in singly linked list; doubly linked list adds complexity and space; rejecting negatives loses functionality.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Index normalization preserves existing complexity and correctness [OK]

Hint: Normalize negative indices by adding size before operation [OK]

Common Mistakes:

• Trying backward traversal in singly linked list
• Switching to doubly linked list unnecessarily
• Ignoring negative indices