算法篇：链表之排序

中间节点作为临界值，小的放左边，大的放右边

将两个有序的链表中，串联起来

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    if head == nil {
        return nil
    }
    curr := head
    before := new(ListNode)
    before1 := before
    after := new(ListNode)
    after1 := after
    for curr != nil {
        if curr.Val < x {
            before.Next = curr
            before = before.Next
        } else {
            after.Next = curr
            after= after.Next
        }
        curr = curr.Next
    }
    before.Next = nil
    after.Next = nil
    if after1.Next != nil {
        before.Next = after1.Next // after1记录偏移之前的after首节点位置
    }
    return before1.Next // 原因是before1首节点是一个none的节点。
}
/* 解法：
这个可以拆分成，两个链表，小于x的放到before,大于等于的放到after.
然后将这两个链表拼接起来。
*/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    l1, l2 := new(ListNode),new(ListNode)
    res,res1 := l1,l2
    for head != nil {
        if head.Val < x {
            l1.Next = &ListNode{Val:head.Val}
            l1 = l1.Next
        } else {
            l2.Next = &ListNode{Val:head.Val}
            l2 = l2.Next
        }
        head = head.Next
    }
    l1.Next = res1.Next
    return res.Next
}
// 双指针排序，小于x的放到l1,大于x的放在l2; 最后将两个链表串起来

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode { 
    // 归并写法：1.先拆分，二分法拆分，快慢指针；2.在合并，双指针的方式
    if head == nil || head.Next == nil {
        return head
    }
    // 快慢指针找到对应的中间位置节点
    s,f := head,head.Next // 两个指针不要指向同一个节点
    for f != nil && f.Next != nil {
        s = s.Next
        f = f.Next.Next
    }
    tmp := s.Next
    s.Next = nil 
    // 递归操作左右链表
    l := sortList(head)
    r := sortList(tmp)
    pre := new(ListNode)
    res := pre
    // 合并左右链表
    for l != nil && r != nil {
        if l.Val < r.Val {
            pre.Next = l
            l = l.Next
        } else {
            pre.Next = r
            r = r.Next
        }
        pre = pre.Next
    }
    if l != nil {
        pre.Next = l
    } else if r != nil {
        pre.Next = r
    }
    return res.Next
}