Odd Even Linked List

Medium
2012.

Odd Even Linked List

Odd Even Linked List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Adobe and Bloomberg interviews.

Given the head of a singly linked list, group all the nodes at odd positions first, followed by the nodes at even positions, and return the head of the reordered list. Positions count from 1, so the head is odd and the second node even — this is about positions, not values.

Keep the relative order inside each group. Use O(1) extra space and O(n) time.

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]
Explanation
Positions 1, 3, 5, 7 hold 2, 3, 6, 7; positions 2, 4, 6 hold 1, 5, 4.

Example 3

Input
head = []
Output
[]

Constraints

  • The number of nodes in the list is in the range [0, 10^4]
  • -10^6 <= Node.val <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Odd Even Linked List — Solution in Python, Java & C++

Odd Even Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.

Odd Even Linked List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Adobe and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Two Pointers
  • Asked at: Amazon, Microsoft, Adobe, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the head of a singly linked list, group all the nodes at odd positions first, followed by the nodes at even positions, and return the head of the reordered list. Positions count from 1, so the head is odd and the second node even — this is about positions, not values.

Keep the relative order inside each group. Use O(1) extra space and O(n) time.

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]
Explanation: Positions 1, 3, 5, 7 hold 2, 3, 6, 7; positions 2, 4, 6 hold 1, 5, 4.

Example 3

Input: head = []
Output: []

Constraints

  • The number of nodes in the list is in the range [0, 10^4]
  • -10^6 <= Node.val <= 10^6

Hints for Odd Even Linked List

  1. Hint 1

    Think of the list as two interleaved lists: odd positions and even positions.

  2. Hint 2

    Walk with two pointers, odd and even, each skipping over the other: odd.next = even.next, then even.next = odd.next.

  3. Hint 3

    Remember the head of the even chain before you start, and attach it after the last odd node at the end.

How to solve Odd Even Linked List

Unzip the list into its odd-position chain and its even-position chain in one pass by letting each pointer jump over the other, then join the even chain after the odd one.

Approach

  1. If the list is empty, return it. Set odd = head, even = head.next, evenHead = even.
  2. While even and even.next exist: odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next.
  3. Link odd.next = evenHead and return head.

Why it works

Each step links an odd node to the next odd node (two ahead) and an even node to the next even node, so the two chains keep their original orders. The loop stops when no odd node remains after even, and at that point odd is the last odd-position node, where the even chain belongs.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Positions, not values: an even value at position 1 still goes first.
  • Save evenHead before relinking — head.next will no longer point at it.
  • The loop condition must check even and even.next so odd never becomes null.

Reference solution

Python

from typing import Optional

def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
        return head
    odd, even = head, 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

Java

public static ListNode oddEvenList(ListNode head) {
    if (head == null) return head;
    ListNode odd = head, even = head.next, 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;
}

C++

ListNode* oddEvenList(ListNode* head) {
    if (!head) return head;
    ListNode *odd = head, *even = head->next, *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;
}

JavaScript

var oddEvenList = function(head) {
    if (head === null) return head;
    var odd = head, even = head.next, 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;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 165 two pointers problems · the whole catalogue

Learn the technique: Two Pointers Technique