重排奇偶有序链表
给定一个链表，其中奇数位是升序的，偶数位是降序的，实现链表的排序。
思路
- 将原始链表按奇偶分开（leetcode原题：奇偶链表， 解答：奇偶链表）
- 偶链表是降序的，所以将其逆序（leetcode原题：翻转链表， 解答：翻转链表)
- 合并两个有序链表（leetcode原题：合并两个有序链表， 解答：合并两个有序链表）
代码
代码语言：javascript复制package main
import "fmt"
type Node struct {
Next *Node
Value int
}
func listMerge(head *Node) *Node {
if head == nil || head.Next == nil {
return head
}
// divide
var l1, l2, tmp1, tmp2 *Node
tmp1 = head
tmp2 = head.Next
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 reverse(head *Node) *Node {
var newHead *Node
for head != nil {
tmp := head.Next
head.Next = newHead
newHead = head
head = tmp
}
return newHead
}
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{}
head := dummmy
for _, a := range arr {
head.Next = &Node{Value: a}
head = head.Next
}
return dummmy.Next
}
