#328

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Odd Even Linked List

Reorder a singly linked list by grouping odd-indexed nodes first, followed by even-indexed nodes while preserving relative order.

linked list

Problem Statement

Given the head of a singly linked list, reorder it so that all nodes positioned at odd indices appear before all nodes positioned at even indices. Preserve the original relative order within both the odd and even groups while performing the reordering in-place.

The first node is considered odd, the second node is even, and so on. You must handle edge cases such as empty lists or single-node lists efficiently, ensuring that pointer manipulations do not break the list structure.

Examples

Example 1

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

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

Example details omitted.

Example 2

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

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

Example details omitted.

Constraints

The number of nodes in the linked list is in the range [0, 104].
-106 <= Node.val <= 106

Solution Approach

Initialize Separate Pointers for Odd and Even Nodes

Create two pointers, one for tracking the current odd node and one for the current even node. Store the head of the even list to reconnect later, and start iterating from the head to segregate nodes into odd and even sublists while updating next pointers.

Iterate and Reconnect Nodes

Traverse the linked list, updating the next pointers of odd nodes to skip the next even node and point to the following odd node, and similarly update even nodes. Continue until the end of the list is reached, maintaining the correct sequence and avoiding cycles or broken links.

Combine Odd and Even Sublists

Once the traversal is complete, attach the head of the even sublist to the end of the odd sublist. Ensure that the last even node points to null to terminate the linked list properly. This step finalizes the in-place reordering without additional memory allocation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited exactly once. Space complexity is O(1) since no additional data structures are used beyond a few pointers, making this approach optimal for in-place reordering.

What Interviewers Usually Probe

Look for in-place pointer manipulations without using extra arrays or lists.
Check whether relative ordering of odd and even nodes is preserved.
Watch for edge cases like empty lists, single-node lists, or lists with only even nodes.

Common Pitfalls or Variants

Common pitfalls

Failing to reconnect the even sublist to the odd sublist at the end.
Breaking the linked list by incorrectly updating next pointers, leading to cycles or null references.
Assuming node values determine odd/even instead of node positions, which is a common misinterpretation.

Follow-up variants

Reordering nodes so that all nodes at prime indices appear before non-prime indices.
Segregating linked list nodes based on alternating property, such as positive and negative values, instead of odd and even positions.
Perform the reordering using a recursive approach instead of iterative pointer manipulation.

FAQ

What is the main challenge in Odd Even Linked List?

The primary challenge is correctly manipulating pointers in a single pass to separate odd and even nodes without losing the original relative order.

Can I solve Odd Even Linked List with extra arrays?

Yes, but using extra arrays increases space complexity and is generally discouraged in interviews that focus on in-place pointer manipulation.

Does node value affect whether it is odd or even?

No, the odd and even grouping is based on node positions, not the values stored in the nodes.

What edge cases should I consider?

Empty lists, single-node lists, and lists with only even or only odd nodes are critical edge cases to handle correctly.

How do I merge the odd and even sublists safely?

Keep a reference to the head of the even sublist, and after processing all nodes, set the next pointer of the last odd node to this even head, ensuring the last even node points to null.

terminal

Solution

Solution 1: Single Pass

We can use two pointers $a$ and $b$ to represent the tail nodes of the odd and even nodes respectively. Initially, pointer $a$ points to the head node $head$ of the list, and pointer $b$ points to the second node $head.next$ of the list. In addition, we use a pointer $c$ to point to the head node $head.next$ of the even nodes, which is the initial position of pointer $b$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        a = head
        b = c = head.next
        while b and b.next:
            a.next = b.next
            a = a.next
            b.next = a.next
            b = b.next
        a.next = c
        return head

Continue Practicing

#355 design twitter #382 linked list random node #237 delete node in a linked list