Problem statement

You are given the head of a linked list of positive integers. Rearrange the nodes so that every node holding an even value comes before every node holding an odd value.

The relative order of the even nodes must stay as it was, and so must the relative order of the odd nodes. Return the head of the rearranged list.

Example 1

Input: head = [17,15,8,9,2,4,6]
Output: [8,2,4,6,17,15,9]
Explanation: The even values 8, 2, 4, 6 move to the front in their original order, followed by the odd values 17, 15, 9.

Example 2

Input: head = [1,9,1]
Output: [1,9,1]
Explanation: There are no even values, so the list is unchanged.

Example 3

Input: head = [12,3,10,7]
Output: [12,10,3,7]
Explanation: Evens 12, 10 first, then odds 3, 7.

Constraints

• The number of nodes in the list is in the range [1, 10^5]
• 1 <= Node.val <= 10^5

Hints for Segregate Even and Odd Nodes in a Linked List

1. Hint 1

   The result is two sublists glued together: the even nodes in order, then the odd nodes in order.

2. Hint 2

   Build both sublists as you walk the original list once, appending each node to the tail of the sublist it belongs to.

3. Hint 3

   Dummy heads for the two sublists avoid special cases; at the end link the even tail to the first odd node and terminate the odd tail.

How to solve Segregate Even and Odd Nodes in a Linked List

A stable partition of a linked list needs no swapping: detach each node and append it to one of two growing lists — evens and odds — then concatenate them.

Approach

1. Create dummy heads evenHead and oddHead, with tails e and o starting at them.
2. For each node of the list, append it to e if its value is even, otherwise to o, advancing that tail.
3. Set o.next = null (the last odd node may still point into the old list), then e.next = oddHead.next.
4. Return evenHead.next.

Why it works

Nodes are appended in the order they are met, so each sublist preserves its original relative order, and every node lands in exactly one sublist. Joining evens before odds gives exactly the required arrangement.

Complexity

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

Pitfalls

• Forgetting to terminate the odd tail creates a cycle when the last node of the original list is even.
• If there are no even nodes, evenHead.next is the odd list itself — the dummy makes that case free.

Reference solution

Python

from typing import Optional

def divide(head: Optional[ListNode]) -> Optional[ListNode]:
    even_head, odd_head = ListNode(0), ListNode(0)
    e, o = even_head, odd_head
    while head:
        if head.val % 2 == 0:
            e.next = head
            e = head
        else:
            o.next = head
            o = head
        head = head.next
    o.next = None
    e.next = odd_head.next
    return even_head.next

Java

public static ListNode divide(ListNode head) {
    ListNode evenHead = new ListNode(0), oddHead = new ListNode(0);
    ListNode e = evenHead, o = oddHead;
    for (; head != null; head = head.next) {
        if (head.val % 2 == 0) { e.next = head; e = head; }
        else { o.next = head; o = head; }
    }
    o.next = null;
    e.next = oddHead.next;
    return evenHead.next;
}

C++

ListNode* divide(ListNode* head) {
    ListNode evenHead(0), oddHead(0);
    ListNode *e = &evenHead, *o = &oddHead;
    for (; head; head = head->next) {
        if (head->val % 2 == 0) { e->next = head; e = head; }
        else { o->next = head; o = head; }
    }
    o->next = nullptr;
    e->next = oddHead.next;
    return evenHead.next;
}

JavaScript

var divide = function(head) {
    var evenHead = new ListNode(0), oddHead = new ListNode(0);
    var e = evenHead, o = oddHead;
    for (; head !== null; head = head.next) {
        if (head.val % 2 === 0) { e.next = head; e = head; }
        else { o.next = head; o = head; }
    }
    o.next = null;
    e.next = oddHead.next;
    return evenHead.next;
};

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

More two pointers problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Rotate a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Swapping Nodes in a Linked List Medium
• Merge In Between Linked Lists Medium