Odd Even Linked List

1. Problem Description

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

The first node is considered odd-indexed, the second node even-indexed, and so on.

The relative order within both the odd and even groups must remain the same as in the input.

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

2. Approach

3. Implementation

3.1. Merge

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    i := 1
    current := head
    oddDummyHead :=  &ListNode{}
    o := oddDummyHead
    evenDummyHead := &ListNode{}
    e := evenDummyHead
    for current != nil {
        next := current.Next
        current.Next = nil
        if i % 2 == 1 {
            o.Next = current
            o = o.Next
        } else {
            e.Next = current
            e = e.Next
        }
        i++
        current = next
    }
    o.Next = evenDummyHead.Next
    return oddDummyHead.Next
}

4. References

• 328. Odd Even Linked List - LeetCode