LeetCode - #86 分隔链表

这篇具有很好参考价值的文章主要介绍了LeetCode - #86 分隔链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


LeetCode - #86 分隔链表

前言

我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 83 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。

不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。

难度水平:中等

1. 描述

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

2. 示例

示例 1

LeetCode - #86 分隔链表

输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]

示例 2

输入:head = [2,1], x = 2
输出:[1,2]

约束条件:

  • 链表中节点的数目在范围 [0, 200]
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

3. 答案

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class PartitionList {
    func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
        let prevDummy = ListNode(0), postDummy = ListNode(0)
        var prev = prevDummy, post = postDummy
        
        var node = head
        
        while node != nil {
            let next = node!.next
            node!.next = nil

            if node!.val < x {
                prev.next = node
                prev = prev.next!
            } else {
                post.next = node
                post = post.next!
            }
            node = next
        }
        
        prev.next = postDummy.next
        
        return prevDummy.next
    }
}
  • 主要思想:插入和合并两个列表,使用 dummy 来避免边缘情况。
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

该算法题解的仓库:LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护,我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容,也整理收集优秀的学习资料。文章来源地址https://www.toymoban.com/news/detail-498772.html

到了这里,关于LeetCode - #86 分隔链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣每日一题86:分隔链表

    给你一个链表的头节点  head  和一个特定值   x  ,请你对链表进行分隔,使得所有  小于   x  的节点都出现在  大于或等于   x  的节点之前。 你应当  保留  两个分区中每个节点的初始相对位置。 示例 1: 示例 2: 提示: 链表中节点的数目在范围  [0, 200]  内 -100 = N

    2024年02月07日
    浏览(37)
  • (链表专题) 725. 分隔链表 ——【Leetcode每日一题】

    给你一个头结点为 head 的单链表和一个整数 k ,请你设计一个算法将链表分隔为 k 个连续的部分。 每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。 这 k 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长

    2023年04月17日
    浏览(38)
  • LeetCode刷题之分隔链表(图解➕代码)

            首先直接进入主题,题目链接🔗力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 源代码在最后,有更优解的朋友欢迎在评论里指导我一番! 通过题目分析得出结论:         1. 将链表分为 k个子链表         2. 用一个数组存放这k个子链表, 数组的长度就是k

    2024年02月06日
    浏览(35)
  • Leetcode 2788. 按分隔符拆分字符串

    我们可以先自己模拟一下分隔字符串的过程。如果只是简单的,遇到分隔符,将分隔符前后的子串加入结果的List,那么很显然并没有考虑到一个String中有多个字符串的情况。一种比较容易想到的方法是: 先对List中每个字符串遍历; 对于每个字符串内部,维护一个缓冲区;

    2024年01月21日
    浏览(50)
  • leetcode-2788按分隔符拆分字符串

    题目链接 2788. 按分隔符拆分字符串 - 力扣(LeetCode) 解题思路

    2024年01月21日
    浏览(45)
  • LeetCode.2788. 按分隔符拆分字符串

    题目链接 题目的意思是给我们一个字符串数组和一个分隔符,让我们按照分隔符把字符串数组分割成新的字符串数组。 看到这个描述,这不就是直接就是利用 按照分隔符分割字符串的系统库函数split() ,这个函数的意思就是 把一个字符串按照你给定的分隔符分割成字符串数

    2024年01月23日
    浏览(77)
  • 【奇想星球】重磅!我们的AIGC共创社区平台上线了!

    公众号原文链接 2023年9月10日,我们的平台网站上线了! 奇想星球 | AIGC共创社区平台。网站地址:https://1aigc.cn 兴趣相同,技能互补。 链接共创,让每个价值放大! 功能模块 产品展示、组队招募、开发者圈子、知识广场、关于我们、个人中心 接下来,简单介绍一下我们的故

    2024年02月07日
    浏览(46)
  • 【LeetCode每日一题】2788. 按分隔符拆分字符串

    2024-1-20 2788. 按分隔符拆分字符串 思路: 对于每个单词,使用一个可变字符串 StringBuilder 来构建拆分后的单词。初始时,可变字符串为空。 遍历每个单词的每个字符,如果遇到指定的分隔符,就将可变字符串中的字符构成一个新的单词,并将其添加到结果列表中。然后清空可

    2024年01月21日
    浏览(49)
  • 智能化社区会给我们的生活带来什么新体验?

    智能化社区指的是利用物联网、云计算、大数据、人工智能等新一代信息技术,结合社区场景下的人、事、地、物等多种数据资源,提供面向物业、企业、居民等的社区管理与服务类应用。实际上,智能化社区就是一种集商业、娱乐、教育、医疗等资源于一体的便捷服务模式

    2024年02月15日
    浏览(48)
  • LeetCode 2788.按分隔符拆分字符串:模拟(字符串处理)

    力扣题目链接:https://leetcode.cn/problems/split-strings-by-separator/ 给你一个字符串数组 words 和一个字符 separator ,请你按 separator 拆分 words 中的每个字符串。 返回一个由拆分后的新字符串组成的字符串数组, 不包括空字符串 。 注意 separator 用于决定拆分发生的位置,但它不包含在

    2024年01月21日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包