奇偶链表

1. 题目描述

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题

2. 思路

3. 实现

3.1. 归并

/**
 * 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. 参考

• 328. 奇偶链表 - 力扣（LeetCode）