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

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

3. Consider the following Python code implementing the recursive reorder list approach. Given the input list 1->2->3, what is the printed output after calling reorderList(n1)?

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

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            back.next = None
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

n3 = ListNode(3)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)
reorderList(n1)
curr = n1
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3

B. 1 2 3

C. 1 3 2

D. 3 2 1

Solution

Solution:

1. Step 1: Trace helper calls with input 1->2->3

   Recursion reaches back=null, then unwinds, linking nodes alternately: 1->3->2.

2. Step 2: Verify final list traversal output

   Prints nodes in order: 1 3 2, confirming correct reorder.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches reorder pattern for 3 nodes [OK]

Hint: Small input trace confirms reorder sequence [OK]

Common Mistakes:

• Assuming no reorder happens
• Stopping recursion too early
• Misplacing next pointers

4. Given the following code snippet for reversing nodes in k-groups, and the input list 1->2->3->4 with k=2, what is the value of group_prev.next.val after the first group reversal?

easy

A. 4

B. 1

C. 3

D. 2

Solution

Solution:

1. Step 1: Trace first group reversal

   Input list: 1->2->3->4, k=2. First group is nodes 1 and 2. After reversal, group becomes 2->1.

2. Step 2: Identify group_prev.next after reversal

   Initially, group_prev is dummy pointing to 1. After reversal, group_prev.next points to 2, the new head of reversed group.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First group's head after reversal is node with value 2 [OK]

Hint: First group's head after reversal is the kth node [OK]

Common Mistakes:

• Confusing original head with new head after reversal
• Off-by-one in counting nodes
• Misunderstanding pointer updates

5. Identify the bug in the following code snippet implementing the odd-even linked list rearrangement:

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    # Missing termination of even list
    odd.next = even_head
    return head

What is the consequence of the missing line and how to fix it?

medium

A. The function does not handle empty lists; fix by adding a check for head == None at the start

B. The odd pointer is not updated correctly inside the loop; fix by moving 'odd = odd.next' after even pointer updates

C. The even_head pointer is lost; fix by initializing even_head after the loop instead of before

D. The even list is not terminated with null, causing a cycle; fix by adding 'if even: even.next = None' before linking odd.next

Solution

1. Step 1: Understand pointer termination

   Without setting even.next = None, the even list may still point to old nodes, causing cycles or infinite loops.

2. Step 2: Fix by terminating even list

   Adding 'if even: even.next = None' before linking odd.next ensures even list ends properly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Proper termination prevents cycles and infinite traversal [OK]

Hint: Always terminate the last node's next with None to avoid cycles [OK]

Common Mistakes:

• Forgetting to terminate even list causing infinite loops
• Misplacing pointer updates causing node skips