重排奇偶有序链表

Updated on with 0 views and 0 comments

思路
1. 将原始链表按奇偶分开（leetcode原题：奇偶链表， 解答：奇偶链表
2. 偶链表是降序的，所以将其逆序（leetcode原题：翻转链表， 解答：翻转链表)
3. 合并两个有序链表（leetcode原题：合并两个有序链表， 解答：合并两个有序链表
代码
``````package main

import "fmt"

type Node struct {
Next *Node
Value int
}

}

// divide
var l1, l2, tmp1, tmp2 *Node
l1 = tmp1
l2 = tmp2
for tmp2 != nil && tmp2.Next != nil {
tmp1.Next = tmp2.Next
tmp1 = tmp1.Next

tmp2.Next = tmp1.Next
tmp2 = tmp2.Next
}
tmp1.Next = nil

return merge(l1, reverse(l2))
}

func merge(l1, l2 *Node) *Node {
var res, tmp *Node

for l1 != nil && l2 != nil {
if l1.Value < l2.Value {
if res == nil {
res = l1
tmp = l1
} else {
tmp.Next = l1
tmp = l1
}
l1 = l1.Next
} else {
if res == nil {
res = l2
tmp = l2
} else {
tmp.Next = l2
tmp = l2
}
l2 = l2.Next
}
}

if l1 != nil {
tmp.Next = l1
}
if l2 != nil {
tmp.Next = l2
}
return res
}

}
}

func main() {
h := gen([]int{1, 8, 3, 6, 5, 4, 7, 2, 9})
r := listMerge(h)
printList(r)

h = gen([]int{1, 8, 3, 6, 5, 4, 7, 2})
r = listMerge(h)
printList(r)
}

func printList(h *Node) {
for tmp := h; tmp != nil; tmp = tmp.Next {
fmt.Printf("%d, ", tmp.Value)
}
fmt.Println()
}

func gen(arr []int) *Node {
dummmy := &Node{}