题解 | #排序奇升偶降链表#

1. 首先分割奇偶链表, 变成两个链表 (这一步不会的先去做LeetCode328题奇偶链表)

2. 反转升序链表

3. 合并两个链表即可

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
*/
// 拆分为两个链表然后在逆序然后再归并排即可

func reverse(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head 
    for cur != nil {
        tmp := cur.Next
        cur.Next = pre
        pre = cur
        cur = tmp
    }
    return pre
}

func sortLinkedList( head *ListNode ) *ListNode {
    // write code here
    if head == nil {
        return nil
    }
    O := head
    G := head.Next
    GHead := G
    for G != nil && G.Next != nil {
        O.Next = G.Next
        O = O.Next
        G.Next = O.Next
        G = G.Next
    }
    O.Next = nil
    newHead := reverse(GHead)
    dummyHead := &ListNode{0, nil}
    cur := dummyHead
    for head != nil && newHead != nil {
        if head.Val <= newHead.Val {
            cur.Next = head
            head = head.Next
        }else {
            cur.Next = newHead
            newHead = newHead.Next
        }
        cur = cur.Next
    }
    if head == nil {
        cur.Next = newHead
    }else {
        cur.Next = head
    }
    return dummyHead.Next
}