Odd Even Linked List

🎯

Odd Even Linked List

mediumLINKED_LISTAmazonGoogleFacebook

Imagine you have a queue of people standing in line, and you want to rearrange them so that all people standing in odd positions come first, followed by those in even positions, while preserving their relative order.

💡 This problem involves rearranging nodes in a linked list based on their position (odd or even). Beginners often struggle because it requires careful pointer manipulation without creating new nodes, and understanding how to maintain relative order while re-linking nodes.

📋

Problem Statement

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is considered odd, the second node even, and so on. The relative order inside both the odd and even groups should remain the same.

1 ≤ n ≤ 10^5 (number of nodes in the linked list)Node values can be any integerMust reorder in-place with O(1) extra spaceTime complexity should be O(n)

💡

Example

Input"head = [1, 2, 3, 4, 5]"

Output[1, 3, 5, 2, 4]

Nodes at odd positions 1,3,5 come first, followed by even positions 2,4.

Input"head = [2, 1, 3, 5, 6, 4, 7]"

Output[2, 3, 6, 7, 1, 5, 4]

Odd nodes: 2,3,6,7; Even nodes: 1,5,4; combined preserving order.

• Single node list → output same list
• Two node list → odd node followed by even node
• All nodes have same value → order preserved
• Empty list (head = null) → output null

⚠️

Common Mistakes

Not terminating the even list with null

Leads to cycles or infinite loops when traversing the list

✅ Explicitly set even_curr.next = null after rearrangement

Losing reference to even head

Cannot connect odd list to even list at the end, resulting in incomplete output

✅ Store even head pointer before rearranging even nodes

Incorrectly updating pointers causing nodes to skip or repeat

Output list has missing or duplicated nodes

✅ Carefully update odd.next and even.next in correct order inside the loop

Not handling empty or single-node lists

Code crashes or returns incorrect result on minimal inputs

✅ Add early return checks for head == null or head.next == null

Using recursion without considering stack overflow

Program crashes on large inputs due to deep recursion

✅ Prefer iterative in-place approach for large lists

🧠

Brute Force (Separate Lists and Concatenate)

💡 This approach explicitly separates odd and even nodes into two new lists and then concatenates them. It helps beginners understand the problem by breaking it down into simpler subproblems, even though it uses extra space.

Intuition

Traverse the list once, placing nodes at odd positions into one list and nodes at even positions into another. Then link the odd list's tail to the head of the even list.

Algorithm

1. Create two dummy heads for odd and even lists.
2. Traverse the original list, appending nodes alternately to odd and even lists.
3. After traversal, link the last odd node to the head of the even list.
4. Return the head of the odd list as the new head.

💡 The main challenge is maintaining two separate lists and then joining them without losing any nodes.

</>

Code

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

def oddEvenList(head):
    if not head:
        return None
    odd_dummy = ListNode(0)
    even_dummy = ListNode(0)
    odd_curr, even_curr = odd_dummy, even_dummy
    curr = head
    index = 1
    while curr:
        if index % 2 == 1:
            odd_curr.next = curr
            odd_curr = odd_curr.next
        else:
            even_curr.next = curr
            even_curr = even_curr.next
        curr = curr.next
        index += 1
    even_curr.next = None
    odd_curr.next = even_dummy.next
    return odd_dummy.next

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->2->3->4->5
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = oddEvenList(head)
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1,3,5,2,4]

Line Notes

if not head:Handle empty list edge case early to avoid errors.

odd_dummy = ListNode(0)Create dummy node to simplify odd list construction.

even_dummy = ListNode(0)Create dummy node to simplify even list construction.

while curr:Traverse the entire list node by node.

if index % 2 == 1:Check if current node is at an odd position.

odd_curr.next = currAppend current node to odd list.

even_curr.next = currAppend current node to even list.

even_curr.next = NoneTerminate even list to avoid cycles.

odd_curr.next = even_dummy.nextConnect odd list tail to even list head.

return odd_dummy.nextReturn the head of the rearranged list.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode oddDummy = new ListNode(0);
        ListNode evenDummy = new ListNode(0);
        ListNode oddCurr = oddDummy, evenCurr = evenDummy;
        ListNode curr = head;
        int index = 1;
        while (curr != null) {
            if (index % 2 == 1) {
                oddCurr.next = curr;
                oddCurr = oddCurr.next;
            } else {
                evenCurr.next = curr;
                evenCurr = evenCurr.next;
            }
            curr = curr.next;
            index++;
        }
        evenCurr.next = null;
        oddCurr.next = evenDummy.next;
        return oddDummy.next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode newHead = sol.oddEvenList(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        // Expected output: 1 3 5 2 4
    }
}

Line Notes

if (head == null) return null;Handle empty list early to avoid null pointer exceptions.

ListNode oddDummy = new ListNode(0);Dummy node simplifies odd list construction.

ListNode evenDummy = new ListNode(0);Dummy node simplifies even list construction.

while (curr != null)Traverse all nodes in the list.

if (index % 2 == 1)Identify odd-positioned nodes.

oddCurr.next = curr;Append current node to odd list.

evenCurr.next = curr;Append current node to even list.

evenCurr.next = null;Terminate even list to prevent cycles.

oddCurr.next = evenDummy.next;Link odd list to even list.

return oddDummy.next;Return new head of rearranged list.

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return nullptr;
        ListNode oddDummy(0), evenDummy(0);
        ListNode* oddCurr = &oddDummy;
        ListNode* evenCurr = &evenDummy;
        ListNode* curr = head;
        int index = 1;
        while (curr) {
            if (index % 2 == 1) {
                oddCurr->next = curr;
                oddCurr = oddCurr->next;
            } else {
                evenCurr->next = curr;
                evenCurr = evenCurr->next;
            }
            curr = curr->next;
            index++;
        }
        evenCurr->next = nullptr;
        oddCurr->next = evenDummy.next;
        return oddDummy.next;
    }
};

int main() {
    Solution sol;
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    ListNode* newHead = sol.oddEvenList(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    // Expected output: 1 3 5 2 4
    return 0;
}

Line Notes

if (!head) return nullptr;Handle empty list to avoid null pointer dereference.

ListNode oddDummy(0), evenDummy(0);Dummy nodes simplify list building.

ListNode* oddCurr = &oddDummy;Pointer to track odd list tail.

ListNode* evenCurr = &evenDummy;Pointer to track even list tail.

while (curr)Traverse all nodes in the original list.

if (index % 2 == 1)Check if current node is odd-positioned.

oddCurr->next = curr;Append node to odd list.

evenCurr->next = curr;Append node to even list.

evenCurr->next = nullptr;Terminate even list to avoid cycles.

oddCurr->next = evenDummy.next;Connect odd list to even list.

return oddDummy.next;Return head of rearranged list.

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function oddEvenList(head) {
    if (!head) return null;
    let oddDummy = new ListNode(0);
    let evenDummy = new ListNode(0);
    let oddCurr = oddDummy;
    let evenCurr = evenDummy;
    let curr = head;
    let index = 1;
    while (curr) {
        if (index % 2 === 1) {
            oddCurr.next = curr;
            oddCurr = oddCurr.next;
        } else {
            evenCurr.next = curr;
            evenCurr = evenCurr.next;
        }
        curr = curr.next;
        index++;
    }
    evenCurr.next = null;
    oddCurr.next = evenDummy.next;
    return oddDummy.next;
}

// Test
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const newHead = oddEvenList(head);
let curr = newHead;
const res = [];
while (curr) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1,3,5,2,4]

Line Notes

if (!head) return null;Handle empty list to avoid errors.

let oddDummy = new ListNode(0);Dummy node simplifies odd list construction.

let evenDummy = new ListNode(0);Dummy node simplifies even list construction.

while (curr)Traverse all nodes in the list.

if (index % 2 === 1)Check if node is at odd position.

oddCurr.next = curr;Append node to odd list.

evenCurr.next = curr;Append node to even list.

evenCurr.next = null;Terminate even list to avoid cycles.

oddCurr.next = evenDummy.next;Connect odd list tail to even list head.

return oddDummy.next;Return new head of rearranged list.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list once (O(n)) but create two new lists with new nodes references, so extra space is O(n).

💡 For n=100, this means 100 operations and extra space for 100 nodes, which is inefficient for large inputs.

Interview Verdict: Accepted but not optimal due to extra space

This approach works but uses extra memory, so it's good for understanding but not ideal for interviews.

🧠

Optimal In-Place Rearrangement Using Two Pointers

💡 This approach rearranges the list in-place without extra space by maintaining two pointers for odd and even nodes and linking them as we traverse. It is the standard optimal solution for this problem.

Intuition

Use two pointers to track the last odd and even nodes. Iterate through the list, linking odd nodes together and even nodes together, then connect the odd list to the even list at the end.

Algorithm

1. Check if the list is empty or has only one node; if so, return it.
2. Initialize two pointers: odd pointing to head, even pointing to head.next, and keep a reference to even head.
3. Iterate while even and even.next are not null:
4. Link odd.next to even.next, move odd forward.
5. Link even.next to odd.next, move even forward.
6. After loop, link odd.next to even head to combine lists.
7. Return head as the new list head.

💡 The key is carefully updating pointers to avoid losing nodes and maintaining the relative order.

</>

Code

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

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
    odd.next = even_head
    return head

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = oddEvenList(head)
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1,3,5,2,4]

Line Notes

if not head or not head.next:Handle lists with 0 or 1 node early.

odd = headInitialize odd pointer at first node.

even = head.nextInitialize even pointer at second node.

even_head = evenKeep reference to even list head for final connection.

while even and even.next:Traverse while even nodes and their next exist.

odd.next = even.nextLink current odd node to next odd node.

odd = odd.nextMove odd pointer forward.

even.next = odd.nextLink current even node to next even node.

even = even.nextMove even pointer forward.

odd.next = even_headConnect odd list tail to even list head.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode newHead = sol.oddEvenList(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        // Expected output: 1 3 5 2 4
    }
}

Line Notes

if (head == null || head.next == null) return head;Handle empty or single-node list early.

ListNode odd = head;Start odd pointer at first node.

ListNode even = head.next;Start even pointer at second node.

ListNode evenHead = even;Save even list head for final connection.

while (even != null && even.next != null)Traverse while even nodes and their next exist.

odd.next = even.next;Link odd node to next odd node.

odd = odd.next;Advance odd pointer.

even.next = odd.next;Link even node to next even node.

even = even.next;Advance even pointer.

odd.next = evenHead;Connect odd list tail to even list head.

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

int main() {
    Solution sol;
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    ListNode* newHead = sol.oddEvenList(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    // Expected output: 1 3 5 2 4
    return 0;
}

Line Notes

if (!head || !head->next) return head;Handle empty or single-node list early.

ListNode* odd = head;Initialize odd pointer at first node.

ListNode* even = head->next;Initialize even pointer at second node.

ListNode* evenHead = even;Save even list head for final connection.

while (even && even->next)Traverse while even nodes and their next exist.

odd->next = even->next;Link odd node to next odd node.

odd = odd->next;Advance odd pointer.

even->next = odd->next;Link even node to next even node.

even = even->next;Advance even pointer.

odd->next = evenHead;Connect odd list tail to even list head.

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function oddEvenList(head) {
    if (!head || !head.next) return head;
    let odd = head;
    let even = head.next;
    let evenHead = even;
    while (even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
}

// Test
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const newHead = oddEvenList(head);
let curr = newHead;
const res = [];
while (curr) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1,3,5,2,4]

Line Notes

if (!head || !head.next) return head;Handle empty or single-node list early.

let odd = head;Initialize odd pointer at first node.

let even = head.next;Initialize even pointer at second node.

let evenHead = even;Save even list head for final connection.

while (even && even.next)Traverse while even nodes and their next exist.

odd.next = even.next;Link odd node to next odd node.

odd = odd.next;Advance odd pointer.

even.next = odd.next;Link even node to next even node.

even = even.next;Advance even pointer.

odd.next = evenHead;Connect odd list tail to even list head.

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list once, updating pointers in-place, so time is linear and space is constant.

💡 For n=100, this means 100 operations and no extra memory, making it efficient for large inputs.

Interview Verdict: Accepted and optimal

This is the preferred solution in interviews due to its efficiency and in-place operation.

🧠

Recursive Approach (Not Recommended for Large Inputs)

💡 This approach uses recursion to separate odd and even nodes by index, but it is less efficient and risks stack overflow for large lists. It is useful to understand recursion on linked lists.

Intuition

Recursively process the list, linking odd nodes first, then even nodes, by passing the current index and rearranging pointers accordingly.

Algorithm

1. Define a recursive helper that takes current node and index.
2. If node is null, return null.
3. If index is odd, link current node to recursive call on next node with index+1.
4. If index is even, link current node to recursive call on next node with index+1.
5. After recursion, connect the last odd node to the head of even nodes.
6. Return the head of the odd nodes.

💡 Managing two separate recursive chains and connecting them at the end is tricky and error-prone.

</>

Code

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

def oddEvenList(head):
    def helper(node, index):
        if not node:
            return (None, None)  # (odd_head, even_head)
        odd_head, even_head = helper(node.next, index + 1)
        if index % 2 == 1:
            node.next = odd_head
            return (node, even_head)
        else:
            node.next = even_head
            return (odd_head, node)
    odd_head, even_head = helper(head, 1)
    # Find tail of odd list
    curr = odd_head
    while curr and curr.next:
        curr = curr.next
    if curr:
        curr.next = even_head
    return odd_head

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = oddEvenList(head)
    curr = new_head
    res = []
    while curr:
        res.append(curr.val)
        curr = curr.next
    print(res)  # Expected: [1,3,5,2,4]

Line Notes

def helper(node, index):Recursive helper to process nodes with index tracking.

if not node:Base case: end of list returns empty odd and even heads.

odd_head, even_head = helper(node.next, index + 1)Recursive call to process next node.

if index % 2 == 1:If current node is odd positioned, link to odd list.

node.next = odd_headLink current odd node to previously processed odd nodes.

return (node, even_head)Return updated odd head and even head.

while curr and curr.next:Traverse odd list to find tail for connection.

curr.next = even_headConnect odd list tail to even list head.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    private ListNode oddHead = null;
    private ListNode evenHead = null;

    private ListNode[] helper(ListNode node, int index) {
        if (node == null) return new ListNode[]{null, null};
        ListNode[] heads = helper(node.next, index + 1);
        if (index % 2 == 1) {
            node.next = heads[0];
            return new ListNode[]{node, heads[1]};
        } else {
            node.next = heads[1];
            return new ListNode[]{heads[0], node};
        }
    }

    public ListNode oddEvenList(ListNode head) {
        ListNode[] heads = helper(head, 1);
        ListNode odd = heads[0];
        ListNode even = heads[1];
        ListNode curr = odd;
        while (curr != null && curr.next != null) {
            curr = curr.next;
        }
        if (curr != null) {
            curr.next = even;
        }
        return odd;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode newHead = sol.oddEvenList(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        // Expected output: 1 3 5 2 4
    }
}

Line Notes

private ListNode[] helper(ListNode node, int index)Recursive helper returns odd and even heads as array.

if (node == null) return new ListNode[]{null, null};Base case returns empty lists.

ListNode[] heads = helper(node.next, index + 1);Recursive call to next node.

if (index % 2 == 1)If current node is odd positioned, link to odd list.

node.next = heads[0];Link current odd node to odd list head.

return new ListNode[]{node, heads[1]};Return updated odd and even heads.

while (curr != null && curr.next != null)Find tail of odd list to connect even list.

curr.next = even;Connect odd list tail to even list head.

#include <iostream>
using namespace std;

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

class Solution {
public:
    pair<ListNode*, ListNode*> helper(ListNode* node, int index) {
        if (!node) return {nullptr, nullptr};
        auto heads = helper(node->next, index + 1);
        if (index % 2 == 1) {
            node->next = heads.first;
            return {node, heads.second};
        } else {
            node->next = heads.second;
            return {heads.first, node};
        }
    }

    ListNode* oddEvenList(ListNode* head) {
        auto heads = helper(head, 1);
        ListNode* odd = heads.first;
        ListNode* even = heads.second;
        ListNode* curr = odd;
        while (curr && curr->next) {
            curr = curr->next;
        }
        if (curr) {
            curr->next = even;
        }
        return odd;
    }
};

int main() {
    Solution sol;
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    ListNode* newHead = sol.oddEvenList(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    // Expected output: 1 3 5 2 4
    return 0;
}

Line Notes

pair<ListNode*, ListNode*> helper(ListNode* node, int index)Recursive helper returns pair of odd and even heads.

if (!node) return {nullptr, nullptr};Base case returns empty lists.

auto heads = helper(node->next, index + 1);Recursive call to next node.

if (index % 2 == 1)If current node is odd positioned, link to odd list.

node->next = heads.first;Link current odd node to odd list head.

return {node, heads.second};Return updated odd and even heads.

while (curr && curr->next)Find tail of odd list to connect even list.

curr->next = even;Connect odd list tail to even list head.

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function oddEvenList(head) {
    function helper(node, index) {
        if (!node) return [null, null];
        const [oddHead, evenHead] = helper(node.next, index + 1);
        if (index % 2 === 1) {
            node.next = oddHead;
            return [node, evenHead];
        } else {
            node.next = evenHead;
            return [oddHead, node];
        }
    }
    const [oddHead, evenHead] = helper(head, 1);
    let curr = oddHead;
    while (curr && curr.next) {
        curr = curr.next;
    }
    if (curr) {
        curr.next = evenHead;
    }
    return oddHead;
}

// Test
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const newHead = oddEvenList(head);
let curr = newHead;
const res = [];
while (curr) {
    res.push(curr.val);
    curr = curr.next;
}
console.log(res); // Expected: [1,3,5,2,4]

Line Notes

function helper(node, index)Recursive helper returns odd and even heads as array.

if (!node) return [null, null];Base case returns empty lists.

const [oddHead, evenHead] = helper(node.next, index + 1);Recursive call to next node.

if (index % 2 === 1)If current node is odd positioned, link to odd list.

node.next = oddHead;Link current odd node to odd list head.

return [node, evenHead];Return updated odd and even heads.

while (curr && curr.next)Find tail of odd list to connect even list.

curr.next = evenHead;Connect odd list tail to even list head.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, but recursion uses stack space proportional to n.

💡 For n=1000, this means 1000 recursive calls which risks stack overflow in some languages.

Interview Verdict: Accepted but not recommended due to recursion overhead

Good for understanding recursion but not practical for large inputs or interviews focused on efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal in-place approach is best for interviews due to O(n) time and O(1) space. Brute force is good for understanding, recursion is elegant but risky.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Separate Lists)	O(n)	O(n)	No	Yes	Mention only - never code
2. Optimal In-Place Two Pointers	O(n)	O(1)	No	Yes	Code this approach
3. Recursive Approach	O(n)	O(n) due to recursion stack	Yes	Yes	Mention only, avoid coding

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, followed by the optimal in-place solution. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using separate lists.Step 3: Explain the optimal in-place two-pointer approach.Step 4: Discuss edge cases and test your code.Step 5: If time permits, mention recursive approach and why it's less practical.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of linked list pointer manipulation, ability to optimize space, and handling of edge cases.

Common Follow-ups

• What if the list is doubly linked? → Similar approach but with prev pointers.
• Can you do this with a circular linked list? → Yes, careful with termination conditions.
• How to handle very large lists? → Use optimal in-place approach to save memory.
• What if nodes have additional data? → The approach remains the same; only pointers change.

💡 These follow-ups test your adaptability and deeper understanding of linked list structures.

🔍

Pattern Recognition

When to Use

1) You need to reorder a linked list based on node positions; 2) The problem mentions odd and even indices; 3) Relative order within groups must be preserved; 4) In-place rearrangement is required.

Signature Phrases

group all the nodes with odd indicesfollowed by the nodes with even indicesrelative order inside both groups

NOT This Pattern When

Problems that reorder based on node values or require sorting are different patterns.

Similar Problems

Reorder List - rearranging nodes based on positionPartition List - grouping nodes based on valueSegregate Even Odd Linked List - similar grouping by parity

Practice

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

2. Consider the following buggy recursive code to convert a binary number in a linked list to an integer. Which line contains the subtle bug that causes incorrect output for single-node lists?

medium

A. Line X: using addition instead of bitwise OR to accumulate bits

B. Line 7: base case check for None node

C. Line 3: __init__ method of ListNode

D. Line 9: recursive call with node.next and updated acc

Solution

1. Step 1: Identify the accumulation operation

   The code uses bitwise OR instead of addition to combine bits: acc = (acc << 1) | node.val.

2. Step 2: Understand impact on single-node lists

   Bitwise OR correctly sets bits without carry, ensuring accurate accumulation for all list lengths.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitwise OR correctly sets bits without carry, addition may overflow [OK]

Hint: Use bitwise OR, not addition, to accumulate bits [OK]

Common Mistakes:

• Using + instead of | causes wrong bit accumulation
• Misunderstanding bitwise operations vs arithmetic
• Assuming addition and OR are interchangeable for bits

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. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list

5. Identify the bug in the following code snippet for splitting a linked list into k parts:

medium

A. Line where curr is advanced without checking if curr is None, causing AttributeError.

B. Line where tails[i].next is set to curr without checking if curr is None.

C. Line where tails[i].next is set to None, which breaks the list prematurely.

D. Line where dummy_heads are created, which wastes extra space.

Solution

1. Step 1: Analyze pointer advancement

   Inside the inner loop, curr is advanced with curr = curr.next without checking if curr is None.

2. Step 2: Identify potential error

   If curr is None, accessing curr.next raises AttributeError. The check must happen before advancing curr.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing None check before curr = curr.next causes runtime error [OK]

Hint: Always check curr is not None before accessing curr.next [OK]

Common Mistakes:

• Forgetting None check before pointer advance
• Incorrectly cutting list by setting next to None too early
• Misusing dummy heads