2021-11-07：奇偶链表。给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节

福大大架构师每日一题

发布于 2021-11-16 10:29:29

5120

发布于 2021-11-16 10:29:29

2021-11-07：奇偶链表。给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。力扣328。

答案2021-11-07：

自然智慧即可。拆分成两个链表，然后合并。

时间复杂度：O(N)。

额外空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    head := &ListNode{val: 1}
    head.next = &ListNode{val: 2}
    head.next.next = &ListNode{val: 3}
    head.next.next.next = &ListNode{val: 4}
    head.next.next.next.next = &ListNode{val: 5}
    oddEvenList(head)
    for head != nil {
        fmt.Println(head)
        head = head.next
    }
}

type ListNode struct {
    val  int
    next *ListNode
}

func oddEvenList(head *ListNode) *ListNode {
    var firstOdd *ListNode
    var firstEven *ListNode
    var odd *ListNode
    var even *ListNode
    var next *ListNode
    count := 1
    for head != nil {
        next = head.next
        head.next = nil
        if (count & 1) == 1 {

            firstOdd = twoSelectOne(firstOdd == nil, head, firstOdd)
            if odd != nil {
                odd.next = head
            }
            odd = head
        } else {
            firstEven = twoSelectOne(firstEven == nil, head, firstEven)
            if even != nil {
                even.next = head
            }
            even = head
        }
        count++
        head = next
    }
    if odd != nil {
        odd.next = firstEven
    }
    return twoSelectOne(firstOdd != nil, firstOdd, firstEven)
}

func twoSelectOne(c bool, a, b *ListNode) *ListNode {
    if c {
        return a
    } else {
        return b
    }
}

执行结果如下：