大数据中链表如何进行排序

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

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

/** * 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}