题解 | #单链表的排序#

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
    l := make([]*ListNode, 0)
    cur := head
    for cur != nil {
        l = append(l, cur)
        cur = cur.Next
    }

    sort(l, 0, len(l) - 1)
   
    
    i := 0 
    for i < len(l) {
        if i == len(l) - 1 {
            l[i].Next = nil
        } else {
            l[i].Next = l[i+1]    
        }
        
        i++
    }
    return l[0]
}


// 快排序关键点 
// 1.sort函数刚开始要把左右指针先保存一份
// 2.右边的哨兵先动，动完左边动
// 3.取left个数位对比的target
// 4.跟target对比时，用>=和<=（注意有个等于号），这样第一个是left，肯定能再left++，这样哨兵相遇时，就可以直接跟target位置进行交换
func sort(l []*ListNode, left, right int) {
    if left >= right {
        return 
    } 
    
    target := left
    baseRight := right
    for left < right {
        for l[right].Val >= l[target].Val && left < right {
            right--
        }
        
        for l[left].Val <= l[target].Val && left < right {
            left++
        }
        
        if left < right {
           tmp := l[left]
           l[left] = l[right]
           l[right] = tmp 
        }

    }
    
    tmp := l[left]
    l[left] = l[target]
    l[target] = tmp
    
    sort(l, target, left - 1)
    sort(l, left + 1, baseRight)    
        
    
    
}