题解 | #给单链表加一#

1. 首先将链表分为奇偶两个链表
2. 偶链表进行反转
3. 再将奇偶两个升序数组升序合并

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
*/
func sortLinkedList( head *ListNode ) *ListNode {
    // write code here  
    jHead,oHead := &ListNode{},&ListNode{}
    
    j,o := jHead,oHead 
    for head != nil && head.Next != nil {
        j.Next = head
        o.Next = head.Next
        j = j.Next
        o = o.Next
        head = head.Next.Next
    }
    if head != nil {
        j.Next = head
        j = j.Next
    }
    
    o.Next = nil
    j.Next = nil
    
    jHead = jHead.Next 
    oHead = resver(oHead.Next)
    return f(jHead,oHead)
}

func resver( head *ListNode ) *ListNode{
    if head == nil || head.Next == nil {
        return head
    }
    
    last := resver(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last
}

func f(one,two *ListNode ) *ListNode {
    dumny := &ListNode{}
    p := dumny
    for one != nil && two != nil {
        if one.Val < two.Val {
            p.Next = one
            one = one.Next
        }else{
            p.Next = two
            two = two.Next
        }
        p = p.Next
    }
    if one != nil {
        p.Next = one
    }
    
    if two != nil {
        p.Next = two
    }
    return dumny.Next
}