题解 | #单链表的排序#

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
*/
func sortInList( head *ListNode ) *ListNode { 
    // write code here
	if head == nil || head.Next == nil { //终止条件，空或者1个
		return head
	}
	var left, mid, fast *ListNode //利用快慢指针，2被速度，所以快指针结束时，慢指针跑一半，left指针用于断开链表
	fast = head
	mid = head
	for fast != nil && fast.Next != nil { //空或者下个为空则终止
		if mid.Next != nil {
			left = mid
			mid = mid.Next
		}
		fast = fast.Next.Next
	}

	left.Next = nil //断开

	return merge12(sortInList(head), sortInList(mid)) //递归，merge12返回到上层是其中一个参数值
}

func merge12(p1,p2 *ListNode)*ListNode{
    if p1==nil{
        return p2
    }
    if p2==nil{
        return p1
    }
    dummyList:=new(ListNode)
    cur:=dummyList
    for p1!=nil && p2!=nil{
        if p1.Val< p2.Val{
            cur.Next=p1
            p1=p1.Next
        }else{
            cur.Next=p2
            p2=p2.Next
        }
        cur=cur.Next
    }
    if p1==nil{
        cur.Next=p2
    }
    if p2==nil{
        cur.Next=p1
    }
    return dummyList.Next
}