题解 | #单链表的排序# go + 分治(归并排序)

go + 分治

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 {
        return head
    }
    
    return splitLink(head)
}

func splitLink(head *ListNode) *ListNode {
	// 拆分为只剩下一个节点或者空节点
    if head == nil || head.Next == nil {
        return head
    }
    
    var pre *ListNode
    slow, fast := head, head
    // 通过快慢指针把链表拆分为2部分
    for fast != nil && fast.Next != nil {
        pre = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 通过此处把链表断开为2部分
    pre.Next = nil
    
    // 再使用递归方式分别拆分2部分链表
    left := splitLink(head)
    right := splitLink(slow)
    
    return mergeLink(left, right)
}

func mergeLink(l1, l2 *ListNode) *ListNode {
	// 如果某个节点为空，则直接返回另外一个节点
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    
    // 合并两个有序的链表
    // 原理与合并2个有序数组一样
    // 创建新的空头节点
    newH := &ListNode{}
    node := newH
    
    for l1 != nil && l2 != nil {
        if l1.Val > l2.Val {
            node.Next = l2
            l2 = l2.Next
        }else{
            node.Next = l1
            l1 = l1.Next
        }
        node = node.Next
    }
    
    // 直接拼接还没有遍历完，剩下的链表
    // 下面2个 if 只有一个会执行
    if l1 != nil {
        node.Next = l1
    }
    if l2 != nil {
        node.Next = l2
    }
    
    return newH.Next
}