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

小编给大家分享一下大数据中链表如何进行排序,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

创新互联公司成都网站建设按需定制设计,是成都网站制作公司,为成都LED显示屏提供网站建设服务,有成熟的网站定制合作流程,提供网站定制设计服务:原型图制作、网站创意设计、前端HTML5制作、后台程序开发等。成都网站推广热线:028-86922220

算法:

对于链表的排序,一般要设计到拆分合并两步,拆分这一步:

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

合并操作步骤:

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

题目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}

执行结果:

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

以上是“大数据中链表如何进行排序”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!


本文题目:大数据中链表如何进行排序
地址分享:http://pwwzsj.com/article/ppcijo.html