Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonMicrosoftGoogle

Partition List Around Value X

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"head":[1,4,3,2,5,2],"x":3}
Expected[1,2,2,4,3,5]

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

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

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

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

Empty list input should return empty list.

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

Single node list remains unchanged regardless of x.

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

All nodes equal to x remain in original order.

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

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

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

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

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

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

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. You are given a singly linked list where each node contains an additional pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both the next and random pointer structure. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?
easy
A. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.
B. Use a hash map to store original-to-copy node mappings and create the copy in two passes.
C. Use a recursive function with memoization to copy nodes and their random pointers.
D. Traverse the list multiple times, copying nodes and random pointers separately without extra data structures.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires copying a complex linked list with random pointers efficiently.
  2. Step 2: Identify the optimal approach

    Interleaving copied nodes within the original list allows assigning random pointers without extra space, then separating the lists restores the original and creates the copy.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Interleaving nodes achieves O(n) time and O(1) space [OK]
Hint: Interleaving nodes avoids extra space for mapping [OK]
Common Mistakes:
  • Assuming recursion is always optimal
  • Using extra hash maps increases space complexity
  • Trying multiple traversals without mapping fails random pointer assignment
2. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list: 1 -> 2 -> 3, where node 1's random points to node 3, node 2's random points to node 1, and node 3's random is null, what is the value of copy_curr.random.val after the last iteration of the separation step (Step 3)?
easy
A. 1
B. 3
C. None (random pointer is null)
D. 2

Solution

  1. Step 1: Trace Step 1 (Interleaving nodes)

    Original list: 1->2->3. After interleaving: 1->1'->2->2'->3->3'.
  2. Step 2: Trace Step 2 (Assign random pointers)

    Node 1's random points to 3, so 1'.random = 3'. Node 2's random points to 1, so 2'.random = 1'. Node 3's random is null, so 3'.random = null.
  3. Step 3: Trace Step 3 (Separate lists)

    After separation, copy_curr starts at 1'. After last iteration, copy_curr is at 3'. Its random pointer is null, so copy_curr.random.val does not exist.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    copy_curr.random is null after last iteration [OK]
Hint: Random pointers point to copied nodes via original's next [OK]
Common Mistakes:
  • Confusing original and copied nodes during separation
  • Off-by-one error in advancing copy_curr
  • Assuming random pointers remain unchanged
3. Consider the following Python code implementing browser history with two stacks. After executing the sequence of operations below, what is the output of the last back call?
browserHistory = BrowserHistory("leetcode.com")
browserHistory.visit("google.com")
browserHistory.visit("facebook.com")
browserHistory.visit("youtube.com")
print(browserHistory.back(1))
print(browserHistory.back(1))
print(browserHistory.forward(1))
easy
A. "youtube.com"
B. "google.com"
C. "facebook.com"
D. "leetcode.com"

Solution

  1. Step 1: Trace back(1) after visiting youtube.com

    back_stack = ["leetcode.com", "google.com", "facebook.com", "youtube.com"] Pop "youtube.com" to forward_stack, back_stack top is "facebook.com".
  2. Step 2: Trace back(1) again and forward(1)

    Second back(1): pop "facebook.com" to forward_stack, top is "google.com". Forward(1): pop "facebook.com" from forward_stack back to back_stack, top is "facebook.com".
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Last forward returns "facebook.com" as expected [OK]
Hint: Back and forward operations move URLs between stacks correctly [OK]
Common Mistakes:
  • Off-by-one errors in popping stacks
  • Confusing forward and back stacks
  • Returning wrong top element after operations
4. You need to implement a data structure that supports the following operations efficiently: get element by index, add element at head, add element at tail, add element at an arbitrary index, and delete element at an arbitrary index. Which approach best guarantees efficient average-case performance for all these operations?
easy
A. Use a dynamic array and resize it when needed to support all operations.
B. Use a balanced binary search tree keyed by index to support all operations in O(log n).
C. Use a singly linked list with sentinel head and tail pointers, maintaining the size for boundary checks.
D. Use a hash map to store index-to-node mappings for constant time access.

Solution

  1. Step 1: Understand operation requirements

    The problem requires efficient get, add at head, add at tail, add at index, and delete at index operations.
  2. Step 2: Evaluate approaches

    Dynamic arrays have O(n) add/delete at head or arbitrary index due to shifting. Singly linked lists have O(1) add at head/tail but O(n) get and add/delete at arbitrary index. Balanced BSTs keyed by index can support all operations in O(log n) time, providing efficient average-case performance. Hash maps do not maintain order and cannot efficiently support index-based operations.
  3. Step 3: Choose best approach

    Balanced BST keyed by index offers O(log n) for all operations, which is more efficient on average than linked list or array for arbitrary index operations.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Balanced BST supports all required operations efficiently [OK]
Hint: Balanced BST keyed by index supports all operations in O(log n) [OK]
Common Mistakes:
  • Assuming linked list provides efficient arbitrary index access
  • Thinking arrays support O(1) insertions at head
  • Assuming hash maps maintain order
5. What is the time and space complexity of the optimal in-place odd-even linked list rearrangement algorithm for a list of length n?
medium
A. Time: O(n), Space: O(1) because each node is visited once and rearranged in-place
B. Time: O(n log n), Space: O(1) due to sorting nodes by index parity
C. Time: O(n), Space: O(n) due to auxiliary lists for odd and even nodes
D. Time: O(n^2), Space: O(1) because of nested pointer updates

Solution

  1. Step 1: Identify loop iterations

    The while loop advances even and odd pointers through the list, each node visited once -> O(n) time.
  2. Step 2: Analyze space usage

    No extra data structures are created; rearrangement is done by pointer manipulation -> O(1) space.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Linear time and constant space is standard for in-place linked list rearrangement [OK]
Hint: One pass with two pointers -> O(n) time, no extra lists -> O(1) space [OK]
Common Mistakes:
  • Assuming nested loops cause O(n^2) time
  • Confusing auxiliary space with recursion stack
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard