专栏首页灰子学技术算法篇:链表之排序

算法篇:链表之排序

算法:

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

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

合并操作步骤:

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

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

执行结果:

本文分享自微信公众号 - 灰子学技术(huizixueguoxue),作者:灰子学技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法:链表之环形链表

    该类题目的核心点在于如何判断是环形链表,核心思想是:两个人在环上跑步,跑的快的早晚会追上跑的慢的。

    灰子学技术
  • 算法篇:链表之倒数第k个节点

    该类型的题目,核心点在于如何找到倒数第k个节点的位置,典型的操作办法是,双指针的方法。

    灰子学技术
  • 算法篇:链表之合并有序链表

    算法的核心在于两个有序链表的合并操作,K个有序链表的合并只是一个变形题目,先拆分成k/2个有序链表,然后等比数列减少到1个数列。

    灰子学技术
  • Leetcode Golang 141. Linked List Cycle.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88992701

    anakinsun
  • Golang Leetcode 142. Linked List Cycle II.go

    https://blog.csdn.net/anakinsun/article/details/89578434

    anakinsun
  • 【测试左移专栏】从测试左移到工程生产力

    随着互联网行业的发展,质量管理的方向逐渐向生产过程看齐。2017年是TMQ变革的重要年份,本文拟通过一个宏观的视图,给读者展现此次变革的完整思路,希望能带给大家...

    腾讯移动品质中心TMQ
  • 如何安装Spark & TensorflowOnSpark

    对的,你没看错,这是我的一条龙服务,我在入坑填坑无数之后终于成功搭建起了Spark和TensorflowOnSpark的运行环境,并成功运行了示例程序(大概就是...

    用户1148523
  • Spark SQL快速入门系列之Hive

    hive on spark(版本兼容) 官网https://cwiki.apache.org/confluence/display/Hive/Hive+on+S...

    大数据技术与架构
  • 数据结构C#版笔记--单链表(LinkList)

    上一篇学习了"顺序表(SeqList)",这一篇来看下“单链表(LinkList)”。在上一篇的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删...

    菩提树下的杨过
  • 基于无尺度网络模型的启发——一种新型数据中心架构的设想

    无尺度网络(Scale Free Network),在网络理论中指的是一类有特定特征的网络。无尺度网络所具有的特征是:大部分节点只有极少的边连接,只有极小一部分...

    SDNLAB

扫码关注云+社区

领取腾讯云代金券