Partition List Around Value X

▶

Steps

setup

Initialize dummy and pointers

Create a dummy node before head to simplify edge cases. Initialize less_tail and prev to dummy, current to head (node with value 1).

💡 Dummy node helps easily insert nodes at the start without special cases. less_tail tracks the end of the less-than-x partition.

Line:

dummy = ListNode(0)
dummy.next = head
less_tail = dummy
prev = dummy
current = head

💡 Setting up dummy and pointers prepares for in-place rearrangement while preserving original list structure.

compare

Check current node value 1 < x=3

Current node value 1 is less than x. Since less_tail.next == current, move less_tail and prev forward to current, then advance current.

💡 When current is immediately after less_tail, just extend the less-than-x partition by moving pointers forward.

Line:

if current.val < x:
    if less_tail.next == current:
        less_tail = less_tail.next
        prev = current
        current = current.next

💡 Nodes already in correct position extend the less-than-x partition without rearrangement.

compare

Check current node value 4 >= x=3

Current node value 4 is not less than x, so move prev and current forward without changing less_tail.

💡 Nodes greater or equal to x remain in place; just advance pointers to continue traversal.

Line:

else:
    prev = current
    current = current.next

💡 Nodes >= x are skipped for repositioning but traversal continues.

compare

Check current node value 3 >= x=3

Current node value 3 equals x, so again move prev and current forward without repositioning.

💡 Nodes equal to x are treated like greater nodes and remain in place.

Line:

else:
    prev = current
    current = current.next

💡 Traversal continues without changes for nodes >= x.

insert

Current node value 2 < x=3, reposition needed

Current node value 2 is less than x but not immediately after less_tail. Remove current from its place and insert after less_tail.

💡 This step moves a node less than x forward to maintain partition order.

Line:

prev.next = current.next
current.next = less_tail.next
less_tail.next = current
less_tail = current
current = prev.next

💡 Repositioning nodes less than x maintains relative order and partitions list in-place.

advance

Current node value 5 >= x=3, advance pointers

Current node value 5 is not less than x, so move prev and current forward without repositioning.

💡 Nodes >= x remain in place; traversal continues.

Line:

else:
    prev = current
    current = current.next

💡 Traversal continues through nodes >= x without changes.

insert

Current node value 2 < x=3, reposition needed

Current node value 2 is less than x and not immediately after less_tail. Remove current and insert after less_tail.

💡 Another repositioning to maintain partition order and relative order of less-than-x nodes.

Line:

prev.next = current.next
current.next = less_tail.next
less_tail.next = current
less_tail = current
current = prev.next

💡 In-place repositioning preserves order and partitions list correctly.

traverse

Traversal complete, current is null

Current pointer reached null, indicating end of list traversal. Partitioning is complete.

💡 Traversal ends when current is null, meaning all nodes have been processed.

Line:

while current:
    ...
return dummy.next

💡 All nodes have been examined and repositioned as needed.

reconstruct

Return new head of partitioned list

Return dummy.next as the head of the rearranged list, which starts at node with value 1.

💡 Dummy.next points to the start of the partitioned list, skipping the dummy node.

Line:

return dummy.next

💡 The partitioned list head is correctly updated after rearrangement.

reconstruct

Final list order verified

The final linked list order is [1, 2, 2, 4, 3, 5], correctly partitioned around x=3 with relative order preserved.

💡 This confirms the algorithm's correctness and in-place rearrangement.

💡 Partitioning is successful without extra lists, preserving order and list integrity.

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

def partition(head, x):
    if not head:
        return None
    dummy = ListNode(0)  # STEP 1
    dummy.next = head
    less_tail = dummy
    prev = dummy
    current = head
    while current:  # STEP 2-8
        if current.val < x:
            if less_tail.next == current:
                less_tail = less_tail.next  # STEP 2
                prev = current
                current = current.next
            else:
                prev.next = current.next  # STEP 5 & 7
                current.next = less_tail.next
                less_tail.next = current
                less_tail = current
                current = prev.next
        else:
            prev = current  # STEP 3,4,6
            current = current.next
    return dummy.next  # STEP 9

# Driver code
if __name__ == '__main__':
    nodes = [1,4,3,2,5,2]
    dummy = ListNode(0)
    curr = dummy
    for v in nodes:
        curr.next = ListNode(v)
        curr = curr.next
    new_head = partition(dummy.next, 3)
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1,2,2,4,3,5]

📊

Partition List Around Value X - Watch the Algorithm Execute, Step by Step

Watching each pointer move and node rearrangement live helps you understand how the algorithm maintains list integrity while partitioning without extra space.

setup

0

→

1

→

4

→

3

→

2

→

5

→

2

advance

0

→

1

→

4

→

3

→

2

→

5

→

2

advance

0

→

1

→

4

→

3

→

2

→

5

→

2

advance

0

→

1

→

4

→

3

→

2

→

5

→

2

insert

0

→

1

→

4

→

3

→

2

→

5

→

2

advance

0

→

1

→

4

→

3

→

2

→

5

→

2

insert

0

→

1

→

4

→

3

→

2

→

5

→

2

traverse

0

→

1

→

4

→

3

→

2

→

5

→

2

reconstruct

1

→

2

→

2

→

4

→

3

→

5

final

1

→

2

→

2

→

4

→

3

→

5

Result: [1, 2, 2, 4, 3, 5]

Key Takeaways

✓ In-place partitioning can be done by carefully repositioning nodes less than x without extra lists.

This insight is hard to see from code alone because pointer manipulations are subtle and easy to miss.

✓ Maintaining a less_tail pointer allows efficient insertion of nodes less than x while preserving relative order.

Visualizing less_tail movement clarifies how the partition boundary advances.

✓ When current node is immediately after less_tail, no repositioning is needed, simplifying pointer updates.

This condition avoids unnecessary node moves and keeps the algorithm efficient.

Practice

1. You are given a singly linked list where each node contains a binary digit (0 or 1). The linked list represents a binary number with the head as the most significant bit. Which approach guarantees an optimal solution to convert this linked list to its decimal integer value?

easy

A. Iteratively accumulate the decimal value by shifting the current value left by 1 and OR-ing with the current node's bit.

B. Use a greedy approach to pick bits that maximize the decimal value at each step.

C. Traverse the list to build a string of bits, then parse the string as a binary number.

D. Apply dynamic programming to store intermediate decimal values for sublists.

Solution

1. Step 1: Understand the problem constraints

   The linked list represents a binary number with the head as the most significant bit, so the decimal value can be built by processing bits from left to right.

2. Step 2: Identify the optimal approach

   Iteratively shifting the accumulated value left by 1 and OR-ing with the current bit correctly builds the decimal value in O(n) time and O(1) space, without extra string conversions or complex DP.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitwise accumulation matches binary to decimal conversion [OK]

Hint: Bitwise accumulation is optimal for binary to decimal conversion [OK]

Common Mistakes:

• Using string concatenation then parsing wastes time and space
• Greedy approaches don't apply to binary number conversion
• Dynamic programming is unnecessary overhead here

2. You need to implement a browser history feature that supports visiting new URLs, moving backward by a number of steps, and moving forward by a number of steps. Which data structure approach best supports efficient visit, back, and forward operations with minimal time complexity?

easy

A. Using a single list with an index pointer to track the current page, slicing the list on visits to discard forward history.

B. Using a queue to store all visited URLs and dequeuing when moving back or forward.

C. Using a doubly linked list where each node stores a URL and pointers to previous and next pages.

D. Using two stacks: one for back history and one for forward history, pushing and popping URLs as navigation occurs.

Solution

1. Step 1: Understand operation requirements

   Visit must discard forward history, back and forward must move efficiently without scanning the entire history.

2. Step 2: Evaluate data structures

   Two stacks allow O(1) amortized push/pop for visit, back, and forward, efficiently managing history and forward pages.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two stacks handle forward/back navigation efficiently [OK]

Hint: Two stacks efficiently manage back and forward navigation [OK]

Common Mistakes:

• Using a single list with slicing causes O(n) visit time
• Doubly linked list is correct but more complex
• Queue does not support backward navigation efficiently

3. You are given a singly linked list and need to reorder it so that the nodes are arranged in the sequence: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Store all nodes in an array, then reorder by reassigning next pointers using two pointers from ends.

B. Use a greedy approach by alternating nodes from the start and end without modifying the list structure.

C. Use dynamic programming to store intermediate reorder states and build the final list.

D. Find the middle of the list, reverse the second half, then merge the two halves alternately.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reordering nodes in a specific pattern without extra space overhead.

2. Step 2: Evaluate approaches for time and space

   Finding the middle, reversing the second half, and merging achieves O(n) time and O(1) space, unlike storing nodes or DP which use extra space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal approach uses middle finding and reversing [OK]

Hint: Middle + reverse + merge is classic reorder pattern [OK]

Common Mistakes:

• Thinking greedy pointer swaps suffice
• Using extra arrays unnecessarily
• Confusing DP with linked list reorder

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

5. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.

class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

medium

A. Line where back_stack.append(url) is called in visit

B. Line where forward_stack.clear() should be called but is missing in visit

C. Line where back_stack.pop() is called in back method

D. Line where forward_stack.pop() is called in forward method

Solution

1. Step 1: Identify visit method behavior

   Visit appends new URL but does not clear forward_stack, so forward history remains outdated.

2. Step 2: Understand impact on forward navigation

   Without clearing forward_stack, forward() returns stale pages that should have been discarded.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Clearing forward_stack on visit is essential to maintain correct forward history [OK]

Hint: Visit must clear forward history to avoid stale pages [OK]

Common Mistakes:

• Forgetting to clear forward stack on visit
• Incorrectly popping from back stack
• Mismanaging stack boundaries