Odd-Even Linked List

Regroup a singly-linked list so all odd-positioned nodes come before all even-positioned nodes.

Given the head of a singly-linked list, group all the nodes that sit at odd positions together, followed by all the nodes at even positions, and return the reordered list.

Positions are 1-indexed: the head is position 1, the next node is position 2, and so on.

The relative order of the nodes within the odd group and within the even group must be preserved from the original list. You must solve it in-place without allocating extra nodes, and the algorithm should run in O(1) extra space and O(L) time, where L is the number of nodes.

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]

Example 3

Input: head = []

Output: []

Explanation: An empty list has no nodes to regroup.

Constraints

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

Hints

Companies

No companies reported yet.

Discussion

Loading discussion...

class Solution {
    public ListNode oddEvenList(ListNode head) {
        // your code here
        return head;
    }
}

Test results

No test cases yet.