Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonMicrosoftGoogle

Partition List Around Value X

Choose your preparation mode4 modes available
🎯
Partition List Around Value X
mediumLINKED_LISTAmazonMicrosoftGoogle

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.

💡 This problem involves rearranging nodes in a linked list based on a pivot value. Beginners often struggle because linked lists require pointer manipulation rather than simple indexing, and preserving relative order adds complexity.
📋
Problem Statement

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
💡
Example
Input"head = [1,4,3,2,5,2], x = 3"
Output[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.

  • All nodes less than x → list remains unchanged
  • All nodes greater or equal to x → list remains unchanged
  • List with only one node → output is the same node
  • List with all nodes equal to x → list remains unchanged
⚠️
Common Mistakes
Not terminating the greater list with null

Leads to cycles or incorrect list traversal

✅ Set greater.next = null after partitioning

Connecting less list to greater list before finishing traversal

May lose nodes or cause incorrect ordering

✅ Only connect after fully traversing and partitioning

Using arrays but forgetting to preserve relative order

Output list order differs from input order within partitions

✅ Append nodes in order encountered to less and greater arrays

In-place rearrangement pointer errors (e.g., skipping nodes)

Leads to lost nodes or corrupted list

✅ Carefully update prev and current pointers after each move

Not handling empty or single-node lists

Null pointer exceptions or incorrect output

✅ Add checks for null head and single node cases

🧠
Brute Force (Extract and Rebuild Using Arrays)
💡 This approach exists to build intuition by simplifying the linked list problem into array manipulation, which is easier to understand but inefficient for large inputs.

Intuition

Extract all node values into an array, reorder the array by partitioning around x, then rebuild the linked list from the reordered array.

Algorithm

  1. Traverse the linked list and store all node values in an array.
  2. Create two arrays: one for values less than x, one for values greater or equal to x.
  3. Concatenate the two arrays to form the partitioned sequence.
  4. Rebuild the linked list from the concatenated array and return the new head.
💡 This approach is straightforward but requires extra space and multiple passes, which is easy to implement but not optimal.
</>
Code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def partition(head, x):
    less = []
    greater_equal = []
    current = head
    while current:
        if current.val < x:
            less.append(current.val)
        else:
            greater_equal.append(current.val)
        current = current.next
    dummy = ListNode(0)
    current = dummy
    for val in less + greater_equal:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->4->3->2->5->2
    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)
    # Print result
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1,2,2,4,3,5]
Line Notes
less = []Initialize list to hold values less than x
greater_equal = []Initialize list to hold values greater or equal to x
while current:Traverse the entire linked list to extract values
if current.val < x:Partition values based on comparison with x
dummy = ListNode(0)Create dummy node to simplify list reconstruction
for val in less + greater_equal:Rebuild linked list preserving partition order
return dummy.nextReturn head of the newly constructed partitioned list
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public ListNode partition(ListNode head, int x) {
        List<Integer> less = new ArrayList<>();
        List<Integer> greaterEqual = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                less.add(current.val);
            } else {
                greaterEqual.add(current.val);
            }
            current = current.next;
        }
        ListNode dummy = new ListNode(0);
        current = dummy;
        for (int val : less) {
            current.next = new ListNode(val);
            current = current.next;
        }
        for (int val : greaterEqual) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        int[] nodes = {1,4,3,2,5,2};
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int v : nodes) {
            curr.next = new ListNode(v);
            curr = curr.next;
        }
        Solution sol = new Solution();
        ListNode newHead = sol.partition(dummy.next, 3);
        curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println(); // Expected: 1 2 2 4 3 5
    }
}
Line Notes
List<Integer> less = new ArrayList<>();Store values less than x for partitioning
List<Integer> greaterEqual = new ArrayList<>();Store values greater or equal to x
while (current != null)Traverse linked list to extract values
if (current.val < x)Partition values based on comparison
ListNode dummy = new ListNode(0);Dummy node to simplify list reconstruction
for (int val : less)Rebuild list nodes for less partition
return dummy.next;Return head of reconstructed partitioned list
#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        vector<int> less, greaterEqual;
        ListNode* current = head;
        while (current) {
            if (current->val < x) {
                less.push_back(current->val);
            } else {
                greaterEqual.push_back(current->val);
            }
            current = current->next;
        }
        ListNode dummy(0);
        current = &dummy;
        for (int val : less) {
            current->next = new ListNode(val);
            current = current->next;
        }
        for (int val : greaterEqual) {
            current->next = new ListNode(val);
            current = current->next;
        }
        return dummy.next;
    }
};

int main() {
    int nodes[] = {1,4,3,2,5,2};
    ListNode dummy(0);
    ListNode* curr = &dummy;
    for (int v : nodes) {
        curr->next = new ListNode(v);
        curr = curr->next;
    }
    Solution sol;
    ListNode* newHead = sol.partition(dummy.next, 3);
    curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl; // Expected: 1 2 2 4 3 5
    return 0;
}
Line Notes
vector<int> less, greaterEqual;Separate vectors to hold partitioned values
while (current)Traverse linked list to extract values
if (current->val < x)Partition values by comparison with x
ListNode dummy(0);Dummy node to simplify list reconstruction
for (int val : less)Rebuild linked list nodes for less partition
return dummy.next;Return head of the new partitioned list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function partition(head, x) {
    const less = [];
    const greaterEqual = [];
    let current = head;
    while (current !== null) {
        if (current.val < x) {
            less.push(current.val);
        } else {
            greaterEqual.push(current.val);
        }
        current = current.next;
    }
    const dummy = new ListNode(0);
    current = dummy;
    for (const val of less.concat(greaterEqual)) {
        current.next = new ListNode(val);
        current = current.next;
    }
    return dummy.next;
}

// Driver code
const nodes = [1,4,3,2,5,2];
const dummy = new ListNode(0);
let curr = dummy;
nodes.forEach(v => {
    curr.next = new ListNode(v);
    curr = curr.next;
});
const newHead = partition(dummy.next, 3);
let res = [];
curr = newHead;
while (curr !== null) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1,2,2,4,3,5]
Line Notes
const less = [];Array to hold values less than x
const greaterEqual = [];Array to hold values greater or equal to x
while (current !== null)Traverse linked list to extract values
if (current.val < x)Partition values by comparison
const dummy = new ListNode(0);Dummy node to simplify reconstruction
for (const val of less.concat(greaterEqual))Rebuild linked list preserving order
return dummy.next;Return head of the new partitioned list
⏱
Complexity
TimeO(n)
SpaceO(n)

We traverse the list once to extract values (O(n)), then rebuild the list in O(n). Extra space is used for arrays storing node values.

💡 For n=100,000 nodes, this means about 200,000 operations plus memory for arrays, which is inefficient but straightforward.
Interview Verdict: Accepted but not optimal

This approach works but uses extra space and multiple passes, so it's a good starting point but interviewers expect better.

🧠
Better Approach (Two Linked Lists with Dummy Heads)
💡 This approach improves space by using linked lists directly instead of arrays, preserving order and avoiding extra memory for values.

Intuition

Create two separate linked lists: one for nodes less than x and one for nodes greater or equal to x, then connect them at the end.

Algorithm

  1. Initialize two dummy nodes: lessHead and greaterHead.
  2. Traverse the original list, appending nodes to less or greater list based on their value.
  3. Connect the less list's tail to the head of the greater list.
  4. Set the greater list's tail next pointer to null and return lessHead.next.
💡 This approach requires careful pointer manipulation but is efficient and preserves order without extra space for values.
</>
Code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def partition(head, x):
    less_head = ListNode(0)
    greater_head = ListNode(0)
    less = less_head
    greater = greater_head
    current = head
    while current:
        if current.val < x:
            less.next = current
            less = less.next
        else:
            greater.next = current
            greater = greater.next
        current = current.next
    greater.next = None
    less.next = greater_head.next
    return less_head.next

# 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]
Line Notes
less_head = ListNode(0)Dummy node to start less-than-x list
greater_head = ListNode(0)Dummy node to start greater-or-equal list
while current:Traverse original list once
if current.val < x:Append node to less list preserving order
greater.next = NoneTerminate greater list to avoid cycles
less.next = greater_head.nextConnect less list to greater list
return less_head.nextReturn head of the combined partitioned list
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode lessHead = new ListNode(0);
        ListNode greaterHead = new ListNode(0);
        ListNode less = lessHead, greater = greaterHead;
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                less.next = current;
                less = less.next;
            } else {
                greater.next = current;
                greater = greater.next;
            }
            current = current.next;
        }
        greater.next = null;
        less.next = greaterHead.next;
        return lessHead.next;
    }

    public static void main(String[] args) {
        int[] nodes = {1,4,3,2,5,2};
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int v : nodes) {
            curr.next = new ListNode(v);
            curr = curr.next;
        }
        Solution sol = new Solution();
        ListNode newHead = sol.partition(dummy.next, 3);
        curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println(); // Expected: 1 2 2 4 3 5
    }
}
Line Notes
ListNode lessHead = new ListNode(0);Dummy node for less partition
ListNode greaterHead = new ListNode(0);Dummy node for greater partition
while (current != null)Single pass traversal of original list
if (current.val < x)Append node to less list preserving order
greater.next = null;Terminate greater list to prevent cycles
less.next = greaterHead.next;Connect less list to greater list
return lessHead.next;Return combined partitioned list head
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode lessHead(0), greaterHead(0);
        ListNode* less = &lessHead;
        ListNode* greater = &greaterHead;
        ListNode* current = head;
        while (current) {
            if (current->val < x) {
                less->next = current;
                less = less->next;
            } else {
                greater->next = current;
                greater = greater->next;
            }
            current = current->next;
        }
        greater->next = nullptr;
        less->next = greaterHead.next;
        return lessHead.next;
    }
};

int main() {
    int nodes[] = {1,4,3,2,5,2};
    ListNode dummy(0);
    ListNode* curr = &dummy;
    for (int v : nodes) {
        curr->next = new ListNode(v);
        curr = curr->next;
    }
    Solution sol;
    ListNode* newHead = sol.partition(dummy.next, 3);
    curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl; // Expected: 1 2 2 4 3 5
    return 0;
}
Line Notes
ListNode lessHead(0), greaterHead(0);Dummy nodes to start partitions
while (current)Traverse original list once
if (current->val < x)Append node to less partition preserving order
greater->next = nullptr;Terminate greater list to avoid cycles
less->next = greaterHead.next;Connect less and greater partitions
return lessHead.next;Return head of combined partitioned list
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function partition(head, x) {
    const lessHead = new ListNode(0);
    const greaterHead = new ListNode(0);
    let less = lessHead;
    let greater = greaterHead;
    let current = head;
    while (current !== null) {
        if (current.val < x) {
            less.next = current;
            less = less.next;
        } else {
            greater.next = current;
            greater = greater.next;
        }
        current = current.next;
    }
    greater.next = null;
    less.next = greaterHead.next;
    return lessHead.next;
}

// Driver code
const nodes = [1,4,3,2,5,2];
const dummy = new ListNode(0);
let curr = dummy;
nodes.forEach(v => {
    curr.next = new ListNode(v);
    curr = curr.next;
});
const newHead = partition(dummy.next, 3);
let res = [];
curr = newHead;
while (curr !== null) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1,2,2,4,3,5]
Line Notes
const lessHead = new ListNode(0);Dummy node for less partition
const greaterHead = new ListNode(0);Dummy node for greater partition
while (current !== null)Traverse original list once
if (current.val < x)Append node to less partition preserving order
greater.next = null;Terminate greater list to avoid cycles
less.next = greaterHead.next;Connect less and greater partitions
return lessHead.next;Return head of combined partitioned list
⏱
Complexity
TimeO(n)
SpaceO(1)

Single pass through the list (O(n)) and only constant extra space for dummy nodes and pointers.

💡 For n=100,000 nodes, this means about 100,000 operations and minimal extra memory, making it efficient and scalable.
Interview Verdict: Accepted and optimal in time and space

This is the preferred approach in interviews because it is efficient and uses constant extra space.

🧠
In-Place Rearrangement Without Extra Lists (Less Common)
💡 This approach tries to rearrange nodes in-place by moving nodes less than x to the front during traversal, but it is more complex and error-prone.

Intuition

Iterate through the list, and whenever a node with value less than x is found, move it to the front of the list, preserving relative order by careful pointer updates.

Algorithm

  1. Use pointers to track the last node in the less-than-x partition and the current node.
  2. Traverse the list; when a node less than x is found after the less partition, remove it and insert it after the last less node.
  3. Update pointers accordingly to maintain list integrity.
  4. Return the head of the rearranged list.
💡 This approach requires careful pointer manipulation and is prone to bugs, so it is less common in interviews.
</>
Code
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)
    dummy.next = head
    less_tail = dummy
    prev = dummy
    current = head
    while current:
        if current.val < x:
            if less_tail.next == current:
                less_tail = less_tail.next
                prev = current
                current = current.next
            else:
                prev.next = current.next
                current.next = less_tail.next
                less_tail.next = current
                less_tail = current
                current = prev.next
        else:
            prev = current
            current = current.next
    return dummy.next

# 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]
Line Notes
dummy = ListNode(0)Dummy node to simplify edge cases
less_tail = dummyTracks end of less-than-x partition
prev = dummyTracks node before current for removals
while current:Traverse entire list
if current.val < x:Check if current node should move forward
prev.next = current.nextRemove current node from its position
current.next = less_tail.nextInsert current node after less_tail
less_tail = currentUpdate less_tail to new node
current = prev.nextMove current pointer forward after removal
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode lessTail = dummy;
        ListNode prev = dummy;
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                if (lessTail.next == current) {
                    lessTail = lessTail.next;
                    prev = current;
                    current = current.next;
                } else {
                    prev.next = current.next;
                    current.next = lessTail.next;
                    lessTail.next = current;
                    lessTail = current;
                    current = prev.next;
                }
            } else {
                prev = current;
                current = current.next;
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        int[] nodes = {1,4,3,2,5,2};
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int v : nodes) {
            curr.next = new ListNode(v);
            curr = curr.next;
        }
        Solution sol = new Solution();
        ListNode newHead = sol.partition(dummy.next, 3);
        curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println(); // Expected: 1 2 2 4 3 5
    }
}
Line Notes
ListNode dummy = new ListNode(0);Dummy node to handle edge cases
ListNode lessTail = dummy;Tracks end of less partition
ListNode prev = dummy;Tracks node before current for removals
while (current != null)Traverse entire list
if (current.val < x)Check if current node should move forward
prev.next = current.next;Remove current node from its position
current.next = lessTail.next;Insert current node after lessTail
lessTail = current;Update lessTail pointer
current = prev.next;Advance current after removal
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (!head) return nullptr;
        ListNode dummy(0);
        dummy.next = head;
        ListNode* lessTail = &dummy;
        ListNode* prev = &dummy;
        ListNode* current = head;
        while (current) {
            if (current->val < x) {
                if (lessTail->next == current) {
                    lessTail = lessTail->next;
                    prev = current;
                    current = current->next;
                } else {
                    prev->next = current->next;
                    current->next = lessTail->next;
                    lessTail->next = current;
                    lessTail = current;
                    current = prev->next;
                }
            } else {
                prev = current;
                current = current->next;
            }
        }
        return dummy.next;
    }
};

int main() {
    int nodes[] = {1,4,3,2,5,2};
    ListNode dummy(0);
    ListNode* curr = &dummy;
    for (int v : nodes) {
        curr->next = new ListNode(v);
        curr = curr->next;
    }
    Solution sol;
    ListNode* newHead = sol.partition(dummy.next, 3);
    curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl; // Expected: 1 2 2 4 3 5
    return 0;
}
Line Notes
ListNode dummy(0);Dummy node to simplify edge cases
ListNode* lessTail = &dummy;Tracks end of less partition
ListNode* prev = &dummy;Tracks node before current for removals
while (current)Traverse entire list
if (current->val < x)Check if current node should move forward
prev->next = current->next;Remove current node from its position
current->next = lessTail->next;Insert current node after lessTail
lessTail = current;Update lessTail pointer
current = prev->next;Advance current after removal
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function partition(head, x) {
    if (!head) return null;
    const dummy = new ListNode(0);
    dummy.next = head;
    let lessTail = dummy;
    let prev = dummy;
    let current = head;
    while (current !== null) {
        if (current.val < x) {
            if (lessTail.next === current) {
                lessTail = lessTail.next;
                prev = current;
                current = current.next;
            } else {
                prev.next = current.next;
                current.next = lessTail.next;
                lessTail.next = current;
                lessTail = current;
                current = prev.next;
            }
        } else {
            prev = current;
            current = current.next;
        }
    }
    return dummy.next;
}

// Driver code
const nodes = [1,4,3,2,5,2];
const dummy = new ListNode(0);
let curr = dummy;
nodes.forEach(v => {
    curr.next = new ListNode(v);
    curr = curr.next;
});
const newHead = partition(dummy.next, 3);
let res = [];
curr = newHead;
while (curr !== null) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1,2,2,4,3,5]
Line Notes
const dummy = new ListNode(0);Dummy node to handle edge cases
let lessTail = dummy;Tracks end of less partition
let prev = dummy;Tracks node before current for removals
while (current !== null)Traverse entire list
if (current.val < x)Check if current node should move forward
prev.next = current.next;Remove current node from its position
current.next = lessTail.next;Insert current node after lessTail
lessTail = current;Update lessTail pointer
current = prev.next;Advance current after removal
⏱
Complexity
TimeO(n)
SpaceO(1)

Single pass through the list with pointer rearrangements, no extra space except dummy node.

💡 For n=100,000 nodes, this is efficient but requires careful pointer updates to avoid bugs.
Interview Verdict: Accepted but more complex and error-prone

This approach is less common in interviews due to complexity; two-list method is preferred for clarity.

📊
All Approaches - One-Glance Tradeoffs
💡 The two dummy linked lists approach is the best to code in interviews due to its clarity, efficiency, and safety.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Arrays)O(n)O(n)NoYesMention only - never code
2. Two Dummy Heads (Optimal)O(n)O(1)NoYesCode this approach
3. In-Place RearrangementO(n)O(1)NoYesMention if asked, but avoid coding due to complexity
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then progress to optimal solutions. Practice coding and explaining each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using arrays to partition and rebuild.Step 3: Explain the two dummy linked lists approach for optimal time and space.Step 4: Optionally mention in-place rearrangement and why it's less preferred.Step 5: Code the two-list approach carefully, test with examples and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of linked list pointer manipulation, ability to preserve relative order, and optimization from naive to efficient solutions.

Common Follow-ups

  • What if you cannot use extra space? → Discuss in-place rearrangement or justify two-list approach as O(1) space.
  • How to handle very large lists efficiently? → Two-list approach is optimal with O(n) time and O(1) space.
💡 Follow-ups often test your knowledge of space optimization and edge case handling, common in linked list problems.
🔍
Pattern Recognition

When to Use

1) Need to reorder linked list nodes 2) Partition around a pivot value 3) Preserve relative order 4) Single pass or efficient solution desired

Signature Phrases

partition listnodes less than x come beforepreserve original relative order

NOT This Pattern When

This is not a sorting problem where full order is required; it's a partition preserving relative order.

Similar Problems

Sort List - also involves linked list reorderingRemove Linked List Elements - filtering nodes based on value

Practice

(1/5)
1. 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
2. You are given a singly linked list and asked to reorder it so that all nodes at odd indices appear before nodes at even indices, preserving the relative order within each group. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?
easy
A. Using a stack to push odd nodes and then pop them to reorder the list
B. Sorting the list based on node values and then merging odd and even indexed nodes
C. Using two pointers to rearrange nodes in-place by linking odd and even nodes separately and then concatenating
D. Using a hash map to store nodes by index parity and reconstructing the list from the map

Solution

  1. Step 1: Understand problem constraints

    The problem requires reordering nodes by their position (odd/even indices) without extra space and in linear time.
  2. Step 2: Evaluate approaches

    Only the two-pointer in-place rearrangement achieves O(n) time and O(1) space by relinking nodes without extra data structures.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Two-pointer approach is standard for odd-even linked list rearrangement [OK]
Hint: Two pointers rearranging nodes in-place is optimal [OK]
Common Mistakes:
  • Thinking sorting or extra data structures are needed
  • Assuming extra space is acceptable for optimal
3. You are given a singly linked list and an integer k. The task is to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should remain as is. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?
easy
A. Use a recursive approach that reverses k nodes at a time and recurses on the rest, relying on call stack for reversal.
B. Apply a dynamic programming approach to store reversed sublists and combine them for the final result.
C. Iteratively traverse the list, reversing each group of k nodes using a helper function, and reconnect groups with pointer manipulation.
D. Use a greedy approach that reverses nodes whenever possible without checking group boundaries.

Solution

  1. Step 1: Understand problem constraints

    The problem requires reversing nodes in groups of k, preserving the order of leftover nodes if fewer than k remain.
  2. Step 2: Evaluate approaches

    Recursive approach (A) uses extra stack space and risks overflow; DP (B) is not applicable; greedy (D) fails on partial groups. Iterative with helper (C) reverses groups efficiently with O(1) space.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Iterative helper method is standard optimal solution [OK]
Hint: Iterative helper reversal is optimal for O(1) space [OK]
Common Mistakes:
  • Confusing recursion with iterative approach
  • Assuming DP applies to linked list reversal
  • Ignoring partial group handling
4. 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
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
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