Odd Even Linked List

Med

#0315Time: O(n), where n is the number of nodes in the linked list. We iterate through the list once.Space: O(1) extra space. We only use a constant number of extra pointers (`oddHead`, `evenHead`, `oddTail`, `evenTail`, `curr`) regardless of the input list's size.

Data structures

Linked List

Prompt

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, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1:

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

Example 2:

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

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward way to solve this problem is to conceptually split the original list into two separate lists: one containing all the odd-indexed nodes and another containing all the even-indexed nodes. We can achieve this by iterating through the list and appending each node to the appropriate list. To make list construction easier, we use dummy head nodes for both the odd and even lists. After the traversal, we link the tail of the odd list to the head of the even list.

Algorithm

Handle the edge case: If head is null, return null.
Create two dummy nodes, oddHead and evenHead, to serve as heads for the odd and even lists.
Create tail pointers, oddTail and evenTail, initialized to the dummy heads.
Use a boolean flag isOdd, initialized to true, to track whether the current node belongs to the odd or even group.
Iterate through the original list with a curr pointer starting from head.
Inside the loop:
- If isOdd is true, append curr to the odd list and advance oddTail.
- Otherwise, append curr to the even list and advance evenTail.
- Move curr to the next node and flip the isOdd flag.
After the loop, connect the tail of the odd list to the head of the even list (oddTail.next = evenHead.next).
Crucially, terminate the now-combined list by setting the tail of the even part to null (evenTail.next = null).
Return the head of the modified list, which is oddHead.next.

Walkthrough

We start by creating two dummy nodes, oddHead and evenHead, which will act as sentinel nodes for our odd and even lists. We also maintain oddTail and evenTail pointers to keep track of the last node in each list, allowing for O(1) appends.

We iterate through the original list using a curr pointer and a boolean flag isOdd to determine where to place the current node. If isOdd is true, we append the node to the odd list; otherwise, we append it to the even list. We then advance curr and toggle the flag.

After processing all nodes, the original list structure is effectively partitioned into two chains of nodes. We must terminate the even list by setting evenTail.next to null. Then, we connect the two lists by setting oddTail.next to the first node of the even list, which is evenHead.next.

The head of the reordered list is oddHead.next.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode oddEvenList(ListNode head) {13        if (head == null) {14            return null;15        }16        ListNode oddHead = new ListNode(0);17        ListNode evenHead = new ListNode(0);18        ListNode oddTail = oddHead;19        ListNode evenTail = evenHead;20        21        ListNode curr = head;22        boolean isOdd = true;23        24        while (curr != null) {25            if (isOdd) {26                oddTail.next = curr;27                oddTail = oddTail.next;28            } else {29                evenTail.next = curr;30                evenTail = evenTail.next;31            }32            curr = curr.next;33            isOdd = !isOdd;34        }35        36        // Connect the odd list with the even list37        oddTail.next = evenHead.next;38        // Terminate the combined list39        evenTail.next = null;40        41        return oddHead.next;42    }43}

Complexity

Time

O(n), where n is the number of nodes in the linked list. We iterate through the list once.

Space

O(1) extra space. We only use a constant number of extra pointers (`oddHead`, `evenHead`, `oddTail`, `evenTail`, `curr`) regardless of the input list's size.

Trade-offs

Pros

Conceptually simple and easy to understand.
Clearly separates the logic for handling odd and even nodes.

Cons

Uses dummy nodes, which adds a small amount of memory and code overhead.
The logic involves more pointer variables compared to a more optimized in-place solution.

This is the most efficient approach, which modifies the linked list in-place without using any dummy nodes. The idea is to maintain two pointers, one for the last node of the odd-indexed group (odd) and one for the last node of the even-indexed group (even). We iterate through the list, weaving the odd and even nodes into their respective groups by rearranging the next pointers.

Algorithm

If head is null, return null.
Initialize odd pointer to head.
Initialize even pointer to head.next.
Save the head of the even list: evenHead = even.
Loop as long as even and even.next are not null.
- Set odd.next to even.next to link the next odd node.
- Move odd to odd.next.
- Set even.next to odd.next to link the next even node.
- Move even to even.next.
After the loop, link the tail of the odd list to the head of the even list: odd.next = evenHead.
Return the original head.

Walkthrough

First, we handle the edge cases where the list is empty or has fewer than three nodes, as no reordering is needed. We initialize an odd pointer to head (the first odd node) and an even pointer to head.next (the first even node). We also save a reference to the head of the even list, evenHead = head.next, because we'll need to connect the end of the odd list to it later.

We then enter a loop that continues as long as there are nodes to process, which is checked by even != null && even.next != null. This condition ensures we always have a pair of nodes (an even one followed by an odd one) to rearrange.

Inside the loop:

We link the current odd node to the next odd node, which is even.next. So, odd.next = even.next;.
We advance the odd pointer to this new node: odd = odd.next;.
We link the current even node to the next even node, which is now odd.next. So, even.next = odd.next;.
We advance the even pointer to this new node: even = even.next;.

After the loop terminates, the odd pointer will be at the tail of the odd-node sublist. We connect it to the head of the even-node sublist: odd.next = evenHead;. Finally, we return the original head.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode oddEvenList(ListNode head) {13        if (head == null) {14            return null;15        }16        17        ListNode odd = head;18        ListNode even = head.next;19        ListNode evenHead = even; // Save the head of the even list20        21        // Loop while there's a pair of nodes (even and its successor) to process22        while (even != null && even.next != null) {23            // Link the next odd node24            odd.next = even.next;25            odd = odd.next;26            27            // Link the next even node28            even.next = odd.next;29            even = even.next;30        }31        32        // Connect the end of the odd list to the head of the even list33        odd.next = evenHead;34        35        return head;36    }37}

Complexity

Time

O(n), where n is the number of nodes. We traverse the list once, and each node is visited a constant number of times.

Space

O(1) extra space. We only use a few extra pointers (`odd`, `even`, `evenHead`). This is a true in-place algorithm.

Trade-offs

Pros

Highly efficient in both time and space, meeting the problem constraints perfectly.
Modifies the list in-place without needing extra data structures like dummy nodes.
The code is concise and elegant.

Cons

The pointer manipulation can be slightly harder to visualize and reason about compared to the separate lists approach.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode oddEvenList ( ListNode head ) { if ( head == null ) { return null ; } ListNode a = head ; ListNode b = head . next , c = b ; while ( b != null && b . next != null ) { a . next = b . next ; a = a . next ; b . next = a . next ; b = b . next ; } a . next = c ; return head ; } }

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * oddEvenList ( ListNode * head ) { if ( ! head ) { return nullptr ; } ListNode * a = head ; ListNode * b = head -> next , * c = b ; while ( b && b -> next ) { a -> next = b -> next ; a = a -> next ; b -> next = a -> next ; b = b -> next ; } a -> next = c ; return head ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem