Odd Even Linked List

Q: What is the best time complexity for Odd Even Linked List?

Optimal (two leapfrogging pointers) runs in O(n) time and O(1) extra space. Each node is relinked once.

Q: Which pattern does Odd Even Linked List use?

It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Copy List with Random Pointer, Intersection of Two Linked Lists.

Q: Is there a brute force solution for Odd Even Linked List?

Yes. Brute force (copy values) takes O(n) time and O(n) space. Read every value into an array, then write them back into the same nodes in the new order: first the values at even indices (positions 1, 3, ...), then the ones at odd indices.

Q: Which edge cases should I test for Odd Even Linked List?

Empty list or a single node; Even length versus odd length: the last node of the odd group differs; Values that are themselves odd or even must not change the grouping.

Medium Linked List Miscellaneous Original on LeetCode

Reported atApple Adobe

Odd Even Linked List is a medium linked list problem solved with the miscellaneous pattern. The best approach, optimal (two leapfrogging pointers), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy values) up.

Problem

Given the head of a singly linked list, rearrange it so that all nodes at odd positions (the 1st, 3rd, 5th, …) come first, followed by all nodes at even positions (the 2nd, 4th, …). Return the head of the rearranged list.

Inside each group, keep the original relative order. Positions are counted from 1 and have nothing to do with the node values. Aim for O(1) extra space and O(n) time.

Examples

Example 1

Input: head = [10, 20, 30, 40, 50]
Output: [10, 30, 50, 20, 40]
Why: Positions 1, 3, 5 hold 10, 30, 50; positions 2 and 4 hold 20, 40 and follow them.

Example 2

Input: head = [4, 9, 1, 6]
Output: [4, 1, 9, 6]
Why: Grouping is by position, not by whether the value is odd or even.

Example 3

Input: head = [5, 5]
Output: [5, 5]
Why: With two nodes the order is already odd position then even position.

Constraints

The list has 0 to 10^4 nodes.
-10^6 <= Node.val <= 10^6
Use O(1) extra space and O(n) time for the optimal approach.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (copy values)	`O(n)`	`O(n)`
Optimal (two leapfrogging pointers)	`O(n)`	`O(1)`

1Brute force (copy values)

TimeO(n)Two passes over the list.

SpaceO(n)The array holds all n values.

Read every value into an array, then write them back into the same nodes in the new order: first the values at even indices (positions 1, 3, ...), then the ones at odd indices.

Walk the list and store the values.
Walk the list again, writing vals[0], vals[2], ... and then vals[1], vals[3], ....
Return head.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) vals.add(p.val);
        ListNode p = head;
        for (int start = 0; start < 2; start++) {
            for (int i = start; i < vals.size(); i += 2) {
                p.val = vals.get(i);
                p = p.next;
            }
        }
        return head;
    }
}

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vals = []
        p = head
        while p:
            vals.append(p.val)
            p = p.next
        p = head
        for start in range(2):
            for i in range(start, len(vals), 2):
                p.val = vals[i]
                p = p.next
        return head

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        vector<int> vals;
        for (ListNode* p = head; p != nullptr; p = p->next) vals.push_back(p->val);
        ListNode* p = head;
        for (int start = 0; start < 2; start++) {
            for (int i = start; i < (int)vals.size(); i += 2) {
                p->val = vals[i];
                p = p->next;
            }
        }
        return head;
    }
};

function oddEvenList(head) {
    const vals = [];
    for (let p = head; p !== null; p = p.next) vals.push(p.val);
    let p = head;
    for (let start = 0; start < 2; start++) {
        for (let i = start; i < vals.length; i += 2) {
            p.val = vals[i];
            p = p.next;
        }
    }
    return head;
}

2Optimal (two leapfrogging pointers)

TimeO(n)Each node is relinked once.

SpaceO(1)Only three pointers; nodes are reused.

Split the list into an odd-position chain and an even-position chain in a single pass by relinking: each pointer skips over the other's node. Remember where the even chain starts and hook it after the last odd node.

If the list has fewer than two nodes, return it.
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.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == 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;
    }
}

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        odd, even = head, head.next
        even_head = even
        while even is not None and even.next is not None:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return head

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

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

Edge cases to test

Empty list or a single node
Even length versus odd length: the last node of the odd group differs
Values that are themselves odd or even must not change the grouping

Hints

Hint 1

Positions 1, 3, 5, ... form one chain and positions 2, 4, 6, ... form another. Can you build both chains while walking the list once?

Hint 2

Keep pointers odd and even that leapfrog: odd.next = even.next, then even.next = odd.next. At the end, attach the even chain after the odd chain.

FAQ

What is the best time complexity for Odd Even Linked List?

Optimal (two leapfrogging pointers) runs in O(n) time and O(1) extra space. Each node is relinked once.

Which pattern does Odd Even Linked List use?

It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Copy List with Random Pointer, Intersection of Two Linked Lists.

Is there a brute force solution for Odd Even Linked List?

Yes. Brute force (copy values) takes O(n) time and O(n) space. Read every value into an array, then write them back into the same nodes in the new order: first the values at even indices (positions 1, 3, ...), then the ones at odd indices.

Which edge cases should I test for Odd Even Linked List?

Empty list or a single node; Even length versus odd length: the last node of the odd group differs; Values that are themselves odd or even must not change the grouping.