小编给大家分享一下大数据中链表如何进行排序，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
算法：
对于链表的排序，一般要设计到拆分合并两步，拆分这一步：
中间节点作为临界值，小的放左边，大的放右边
合并操作步骤：
将两个有序的链表中，串联起来
题目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进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
