Odd Even Linked List

▶

Steps

setup

Initialize / Setup

The linked list is created with nodes 1 → 2 → 3 → 4 → 5. The head pointer references node 1.

💡 Setting up the initial list is essential to visualize how nodes will be rearranged.

Line:

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))

💡 The initial structure and head pointer are established for the recursive process.

traverse

Recursive call helper(node=1, index=1)

The helper function is called with node 1 at index 1 (odd). It will recurse on node 2 with index 2.

💡 Each recursive call processes one node and its index to separate odd and even nodes.

Line:

odd_head, even_head = helper(node.next, index + 1)  # node=1, index=1

💡 Recursion moves forward to the next node before rearranging current node's next pointer.

traverse

Recursive call helper(node=2, index=2)

Helper is called with node 2 at index 2 (even). It recurses on node 3 with index 3.

💡 The recursion continues, moving deeper to separate odd and even nodes by index.

Line:

odd_head, even_head = helper(node.next, index + 1)  # node=2, index=2

💡 Recursion depth increases, preparing to rearrange nodes on return.

traverse

Recursive call helper(node=3, index=3)

Helper is called with node 3 at index 3 (odd). It recurses on node 4 with index 4.

💡 Recursion continues to the next node, preparing to separate odd and even nodes.

Line:

odd_head, even_head = helper(node.next, index + 1)  # node=3, index=3

💡 The recursion stack grows deeper, nodes will be rearranged on return.

traverse

Recursive call helper(node=4, index=4)

Helper is called with node 4 at index 4 (even). It recurses on node 5 with index 5.

💡 Recursion continues to the next node, preparing to separate odd and even nodes.

Line:

odd_head, even_head = helper(node.next, index + 1)  # node=4, index=4

💡 The recursion stack is near the end of the list.

traverse

Recursive call helper(node=5, index=5)

Helper is called with node 5 at index 5 (odd). It recurses on null with index 6.

💡 Reached the end of the list; next recursive call will return base case.

Line:

odd_head, even_head = helper(node.next, index + 1)  # node=5, index=5

💡 Base case is imminent, recursion will start returning.

traverse

Base case reached: helper(node=null, index=6)

Helper is called with node null, returns (None, None) for odd and even heads.

💡 Base case stops recursion and starts returning up the call stack.

Line:

if not node:
    return (None, None)  # (odd_head, even_head)

💡 Base case returns empty odd and even lists for further linking.

reconstruct

Return from helper(node=5, index=5) - odd index

Node 5 is odd index, so node.next is set to odd_head (None), returning (node 5, even_head None).

💡 Odd nodes link to the odd list returned from recursion, building odd list backwards.

Line:

if index % 2 == 1:
    node.next = odd_head
    return (node, even_head)  # node=5

💡 Odd nodes are linked to the previously returned odd list, building the odd list recursively.

reconstruct

Return from helper(node=4, index=4) - even index

Node 4 is even index, so node.next is set to even_head (None), returning (odd_head 5, node 4).

💡 Even nodes link to the even list returned from recursion, building even list backwards.

Line:

else:
    node.next = even_head
    return (odd_head, node)  # node=4

💡 Even nodes are linked to the previously returned even list, building the even list recursively.

reconstruct

Return from helper(node=3, index=3) - odd index

Node 3 is odd index, so node.next is set to odd_head (node 5), returning (node 3, even_head node 4).

💡 Odd nodes link to the odd list, continuing to build the odd list.

Line:

if index % 2 == 1:
    node.next = odd_head
    return (node, even_head)  # node=3

💡 Odd list is built by linking current odd node to previously returned odd list head.

reconstruct

Return from helper(node=2, index=2) - even index

Node 2 is even index, so node.next is set to even_head (node 4), returning (odd_head node 3, node 2).

💡 Even nodes link to the even list, continuing to build the even list.

Line:

else:
    node.next = even_head
    return (odd_head, node)  # node=2

💡 Even list is built by linking current even node to previously returned even list head.

reconstruct

Return from helper(node=1, index=1) - odd index

Node 1 is odd index, so node.next is set to odd_head (node 3), returning (node 1, even_head node 2).

💡 Odd nodes link to the odd list, completing the odd list head.

Line:

if index % 2 == 1:
    node.next = odd_head
    return (node, even_head)  # node=1

💡 Odd list is built by linking current odd node to previously returned odd list head.

traverse

Find tail of odd list

Starting from odd_head (node 1), iterate to find the last node in odd list (node 5).

💡 Finding the tail is necessary to connect odd and even lists.

Line:

curr = odd_head
while curr and curr.next:
    curr = curr.next

💡 Traversal locates the last odd node to link even list after it.

connect

Connect tail of odd list to head of even list

Set curr.next (node 5's next) to even_head (node 2), linking odd and even lists.

💡 This step merges the two separated lists into the final reordered list.

Line:

if curr:
    curr.next = even_head

💡 Connecting odd tail to even head completes the odd-even rearrangement.

reconstruct

Return final reordered list head

Return odd_head (node 1) as the head of the reordered list 1 → 3 → 5 → 2 → 4.

💡 The reordered list head is returned for further use or output.

Line:

return odd_head

💡 The reordered list starts at the original head, now rearranged by odd-even positions.

traverse

Traverse final list to collect output

Traverse from head (node 1) through next pointers to collect values in order: 1, 3, 5, 2, 4.

💡 Traversing the final list confirms the correct odd-even rearrangement.

Line:

curr = new_head
while curr:
    res.append(curr.val)
    curr = curr.next

💡 Traversal verifies the final linked list order matches expected output.

traverse

Continue traversal: node 3

Move pointer to node 3, append value 3 to output list.

💡 Stepwise traversal shows output list building incrementally.

Line:

res.append(curr.val)
curr = curr.next

💡 Output list grows as traversal proceeds through reordered nodes.

traverse

Continue traversal: node 5

Move pointer to node 5, append value 5 to output list.

💡 Traversal continues to confirm all nodes are visited in order.

Line:

res.append(curr.val)
curr = curr.next

💡 Traversal confirms odd nodes appear first in output.

traverse

Continue traversal: node 2

Move pointer to node 2, append value 2 to output list.

💡 Traversal now visits even nodes after odd nodes.

Line:

res.append(curr.val)
curr = curr.next

💡 Even nodes follow odd nodes in the output list.

traverse

Finish traversal: node 4 and end

Move pointer to node 4, append value 4 to output list, then reach null ending traversal.

💡 Traversal completes, confirming final output list matches expected.

Line:

res.append(curr.val)
curr = curr.next

💡 Traversal confirms final reordered list is [1, 3, 5, 2, 4].

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:  # STEP 7
            return (None, None)  # (odd_head, even_head)
        odd_head, even_head = helper(node.next, index + 1)  # STEP 2-6
        if index % 2 == 1:  # STEP 8,10,12
            node.next = odd_head
            return (node, even_head)
        else:  # STEP 9,11
            node.next = even_head
            return (odd_head, node)
    odd_head, even_head = helper(head, 1)  # STEP 1
    curr = odd_head  # STEP 13
    while curr and curr.next:
        curr = curr.next
    if curr:  # STEP 14
        curr.next = even_head
    return odd_head  # STEP 15

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

📊

Odd Even Linked List - Watch the Algorithm Execute, Step by Step

Watching each recursive call and pointer reassignment reveals how the list is split and merged without extra space.

advance

1

→

2

→

3

→

4

→

5

traverse

1

→

2

→

3

→

4

→

5

traverse

1

→

2

→

3

→

4

→

5

traverse

1

→

2

→

3

→

4

→

5

traverse

1

→

2

→

3

→

4

→

5

traverse

1

→

2

→

3

→

4

→

5

traverse

1

→

2

→

3

→

4

→

5

connect

5

Result:

Odd head:5

Even head:null

connect

5

→

4

Result:

Odd head:5

Even head:4

connect

3

→

5

→

4

Result:

Odd head:3

Even head:4

connect

3

→

5

→

2

→

4

Result:

Odd head:3

Even head:2

connect

1

→

3

→

5

→

2

→

4

Result:

Odd head:1

Even head:2

traverse

1

→

3

→

5

→

2

→

4

Result:

Odd head:1

Even head:2

connect

1

→

3

→

5

→

2

→

4

advance

1

→

3

→

5

→

2

→

4

traverse

1

→

3

→

5

→

2

→

4

Result: [1]

traverse

1

→

3

→

5

→

2

→

4

Result: [1, 3]

traverse

1

→

3

→

5

→

2

→

4

Result: [1, 3, 5]

traverse

1

→

3

→

5

→

2

→

4

Result: [1, 3, 5, 2]

traverse

1

→

3

→

5

→

2

→

4

Result: [1, 3, 5, 2, 4]

Key Takeaways

✓ The recursive approach separates odd and even nodes by index during the call stack unwind, building two lists simultaneously.

This insight is hard to see from code alone because recursion hides the order of operations until return.

✓ Odd nodes are linked to the previously returned odd list head, and even nodes to the even list head, effectively reversing the list during recursion.

Visualizing pointer reassignments clarifies how the list is rebuilt in correct order.

✓ The final step connects the tail of the odd list to the head of the even list, merging the two sublists into the final reordered list.

Understanding this merge is key to grasping how the algorithm produces the final output.

Practice

1. Given the following code snippet for splitting a linked list into k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?

easy

A. [[1, 2], [3, 4], []]

B. [[1, 2], [3], [4]]

C. [[1, 2], [3], [4, None]]

D. [[1], [2], [3, 4]]

Solution

1. Step 1: Calculate total nodes and part sizes

   Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.

2. Step 2: Assign nodes to parts

   Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of parts equals original list length and sizes differ by at most one [OK]

Hint: Remainder nodes assigned to first parts -> first part larger [OK]

Common Mistakes:

• Assigning remainder nodes to last parts
• Off-by-one in part sizes
• Returning fewer than k parts

2. What is the time complexity of the recursive approach that converts a binary number in a linked list to an integer by accumulating the value with bit shifts?

medium

A. O(n log n) due to bit shifts at each node

B. O(n^2) because recursion stack causes repeated computations

C. O(n) because each node is visited once with constant work

D. O(n) time but O(n^2) space due to recursion stack

Solution

1. Step 1: Analyze time per node

   Each node is processed once, performing a constant number of bit operations (shift and OR).

2. Step 2: Consider recursion overhead

   Recursion depth is n, but no repeated computations occur; each call does O(1) work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Bit shifts are O(1) operations, not O(log n) [OK]

Common Mistakes:

• Assuming bit shifts cost O(log n)
• Confusing recursion stack space with time complexity
• Thinking recursion causes repeated work

3. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.

class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

medium

A. Line where back_stack.append(url) is called in visit

B. Line where forward_stack.clear() should be called but is missing in visit

C. Line where back_stack.pop() is called in back method

D. Line where forward_stack.pop() is called in forward method

Solution

1. Step 1: Identify visit method behavior

   Visit appends new URL but does not clear forward_stack, so forward history remains outdated.

2. Step 2: Understand impact on forward navigation

   Without clearing forward_stack, forward() returns stale pages that should have been discarded.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Clearing forward_stack on visit is essential to maintain correct forward history [OK]

Hint: Visit must clear forward history to avoid stale pages [OK]

Common Mistakes:

• Forgetting to clear forward stack on visit
• Incorrectly popping from back stack
• Mismanaging stack boundaries

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 problem is modified so that nodes can be reused multiple times (i.e., after reversing a group, nodes can appear again in subsequent groups). Which of the following changes to the algorithm correctly handles this scenario?

hard

A. Modify the algorithm to create new nodes for each group reversal to avoid modifying original nodes in place.

B. This problem cannot be solved by reversal; instead, use a queue to simulate repeated node usage.

C. Use recursion with memoization to store reversed groups and reuse them without modifying the original list.

D. Use the same iterative reversal approach but reset pointers to allow reusing nodes in multiple groups.

Solution

1. Step 1: Understand node reuse implication

   Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.

2. Step 2: Evaluate algorithm modifications

   In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.

3. Step 3: Assess other options

   Resetting pointers (A) breaks list integrity; recursion with memoization (C) is complex and not standard; queue simulation (B) does not solve reversal reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Duplicating nodes preserves original list for reuse [OK]

Hint: Node reuse requires duplication, not in-place reversal [OK]

Common Mistakes:

• Trying to reuse nodes in place
• Ignoring list integrity
• Assuming recursion memoization solves reuse