重排奇偶有序链表

给定一个链表，其中奇数位是升序的，偶数位是降序的，实现链表的排序。

思路

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

代码

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
}