大數(shù)據(jù)中鏈表如何進(jìn)行排序

中間節(jié)點(diǎn)作為臨界值，小的放左邊，大的放右邊

將兩個(gè)有序的鏈表中，串聯(lián)起來(lái)

/** * 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首節(jié)點(diǎn)位置    }    return before1.Next // 原因是before1首節(jié)點(diǎn)是一個(gè)none的節(jié)點(diǎn)。}/* 解法：這個(gè)可以拆分成，兩個(gè)鏈表，小于x的放到before,大于等于的放到after.然后將這兩個(gè)鏈表拼接起來(lái)。*/

/** * 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; 最后將兩個(gè)鏈表串起來(lái)

/** * 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    }    // 快慢指針找到對(duì)應(yīng)的中間位置節(jié)點(diǎn)    s,f := head,head.Next // 兩個(gè)指針不要指向同一個(gè)節(jié)點(diǎn)    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}