溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下大數據中鏈表如何進行排序，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
算法：
對于鏈表的排序，一般要設計到拆分合并兩步，拆分這一步：
中間節點作為臨界值，小的放左邊，大的放右邊
合并操作步驟：
將兩個有序的鏈表中，串聯起來
題目1:分隔鏈表
https://leetcode-cn.com/problems/partition-list/submissions/
代碼實現：
/** * 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.然后將這兩個鏈表拼接起來。*/
執行結果：
題目2:
https://leetcode-cn.com/problems/partition-list-lcci/submissions/
代碼實現：
/** * 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; 最后將兩個鏈表串起來
執行結果：
題目3:排序鏈表
https://leetcode-cn.com/problems/sort-list/
代碼實現：
/** * 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}
執行結果：
以上是“大數據中鏈表如何進行排序”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
