Partition List Around Value X

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Arrays)	O(n)	O(n)	No	Yes	Mention only - never code
2. Two Dummy Heads (Optimal)	O(n)	O(1)	No	Yes	Code this approach
3. In-Place Rearrangement	O(n)	O(1)	No	Yes	Mention 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. 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 split a singly linked list into k parts such that the sizes of the parts differ by at most one, and the order of nodes is preserved. Which approach guarantees an optimal solution with minimal passes over the list and clean code structure?

easy

A. Use a greedy approach that assigns nodes to parts until the next part would be larger, then move on.

B. Split the list by repeatedly removing the head node and appending it to parts until all nodes are distributed.

C. Precompute the total length, then split the list in-place using dummy heads and careful pointer manipulation.

D. Apply dynamic programming to decide the best split points to minimize size differences.

Solution

1. Step 1: Understand the problem constraints

   The parts must differ in size by at most one, and the original order must be preserved.

2. Step 2: Evaluate approaches

   Greedy and naive removal approaches do not guarantee minimal passes or clean code. Dynamic programming is unnecessary overhead. Precomputing length and using dummy heads allows a single pass split with clear structure.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Precomputing length and dummy heads -> minimal passes and clean code [OK]

Hint: Precompute length, then split in-place with dummy heads [OK]

Common Mistakes:

• Assuming greedy splitting always works
• Using DP unnecessarily
• Splitting without precomputing length

3. What is the space complexity of the optimal approach that copies a linked list with random pointers by weaving copied nodes into the original list and then separating them?

medium

A. O(n) due to storing copied nodes in a hash map

B. O(n) because each node's random pointer requires extra space

C. O(n) due to recursion stack in the copying process

D. O(1) because no extra data structures are used besides new nodes

Solution

1. Step 1: Identify auxiliary space usage

   The optimal approach weaves copied nodes directly into the original list without using extra hash maps or recursion.

2. Step 2: Confirm space complexity

   Only new nodes are created, which is required output space, so auxiliary space is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No extra data structures or recursion stack used [OK]

Hint: Weaving nodes avoids extra mapping space [OK]

Common Mistakes:

• Confusing output space with auxiliary space
• Assuming recursion is used and adds stack space
• Thinking random pointers require extra space

4. Consider the following buggy code snippet for reversing nodes in k-groups. Which line contains the subtle bug that can cause incorrect output when the list length is not a multiple of k?

medium

A. Line missing the check 'if count < k: break' after counting nodes

B. Line with 'group_next = kth.next' assignment

C. Line with 'while kth.next and count < k:' loop

D. Line with 'tmp.next = group_next' pointer update

Solution

1. Step 1: Identify missing boundary check

   The code does not check if the remaining nodes are fewer than k before reversal.

2. Step 2: Consequence of missing check

   Without 'if count < k: break', partial groups get reversed incorrectly, breaking problem constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing break causes partial group reversal [OK]

Hint: Always check group size before reversal [OK]

Common Mistakes:

• Forgetting to break on partial group
• Misplacing pointer updates
• Assuming kth always valid

5. Suppose the multilevel doubly linked list can contain cycles via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the in-place iterative flattening algorithm correctly handles this scenario without infinite loops?

hard

A. Ignore cycles since the algorithm naturally terminates when curr is null.

B. Remove all child pointers before flattening to break cycles.

C. Use recursion with a depth limit to avoid infinite recursion.

D. Add a visited set to track nodes already processed and skip nodes if revisited.

Solution

1. Step 1: Understand cycle problem

   Cycles via child pointers cause infinite loops if nodes are revisited during flattening.

2. Step 2: Evaluate solutions

   Ignoring cycles (A) causes infinite loops. Removing child pointers (B) loses data. Recursion with depth limit (C) is unreliable. Tracking visited nodes (D) prevents revisiting and infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Visited set prevents infinite loops in cyclic structures [OK]

Hint: Cycle detection requires tracking visited nodes explicitly [OK]

Common Mistakes:

• Assuming no cycles exist in input
• Relying on recursion depth limits
• Ignoring child pointers that create cycles