草庐IT

单手杀穿经典链表题Pt.1——LeetCode天梯渡劫(移除节点,反转链表,中间节点)

乔乔家的龙龙 2023-04-05 原文

目录

传统艺能😎

小编是双非本科大一菜鸟不赘述,欢迎大佬指点江山(QQ:1319365055)
此前博客点我!点我!请搜索博主 【知晓天空之蓝】
乔乔的gitee代码库(打灰人欢迎访问,点我!

🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们,打码路上一路向北,背后烟火,彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区,诚邀各位有志之士的加入!!
社区用户好文均加精(“标兵”文章字数2000+加精,“达人”文章字数1500+加精)
直达: 社区链接点我

你觉得今天打打球没关系,下次你就会觉得明天躺在宿舍玩玩手机也没关系,不要低估你的实力,却不能高估你的毅力,只有优秀成为一种习惯你才不会优柔寡断,唯唯诺诺,当你还没有成功的那一刻,你什么都不是,只有成功之后,你放屁都是香的,你之所以没有这种感觉就是因为你还没有成功。 -------摘自托马斯-酷涛大佬原文

移除链表元素🤔

链接:移除链表元素

题目:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

示例 :
输入:head = [1,2,3,2,1], val = 2
输出:[1,3,1]

思路:
我的评价是有手就行,就相当于链表的删除操作,进行遍历,遍历过程中找到目标值进行覆盖就行,注意一下这里我们采用哨兵位节点,也称为哑节点,开辟出来指向链表头节点,可以使对头节点的操作变简单很多,这个哨兵位节点的值可以不考虑,他只是用来攀搭头结点的舔狗(呜呜)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* curr = dummyHead;//定义哨兵位节点

    while (curr->next) {
        if (curr->next->val == val) {
            curr->next = curr->next->next;//遍历到目标点进行覆盖
        } 
        else 
        {
            curr = curr->next;
        }
    }
    head = dummyHead->next;
    free(dummyHead); //有借有还,记得归还哨兵位节点和申请的空间  

    return head;
}

反转链表🤔

链接:反转链表

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表

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


思路:
1.创建一个新的中间节点我命名为 next ,将当前节点的下一个节点存放在next 节点中
2.链接 next 和当前节点,将 next 指向 当前节点实现反转,将原来指向下一节点的内容销毁掉(头部指向NIULL即可);
3.重复上述过程即可

以上是整体思路实现,而代码实现我们有两条路可以走,分别是迭代和递归,实现思路是一样的:

迭代:

struct ListNode* reverseList(struct ListNode* head){
struct ListNode* next = NULL;
struct ListNode* prev = NULL;
while(head)
{   
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}

递归:

递归又分为了向前递归和向后递归,一般采用从前向后递归:

struct ListNode* reverse(struct ListNode* cur,struct ListNode* prev)
{
if(cur==NULL)
{
    return prev;
}
 struct ListNode* next = cur->next;
cur->next = prev;
return reverse(next,cur); //可以与双指针法对比,其实逻辑是一样的,只是用递归实现而已
}

struct ListNode* reverseList(struct ListNode* head)
{
return reverse(head,NULL);
}

从后向前递归:

struct ListNode* reverseList(struct ListNode* head)
{
if(!head || !head->next)
return head;
struct ListNode* cur =  reverseList(head->next);//反转第二个节点后的所有节点
head->next->next = haed;//反转第二个节点与头节点
head->next = NULL;//头节点处理

return cur;
}

~

链表的中间结点🤔

链接:链表的中间结点

给定一个头结点为 head 的非空单链表,返回链表的中间结点,如果有两个中间结点,则返回第二个中间结点。

奇数个返回中间节点:

偶数个返回了两个节点中的后一个:

思路:
方法一就是老老实实去遍历链表,算出链表长度,再找出中间节点位置,走过去返回他,属于暴力求解,笨且效率不高,这里就不做代码展示;
方法二巧用快慢指针,如下图:

我们定义两个指针,慢指针一次走一步,快指针一次走两步,不管链表节点数是奇是偶,慢指针最后必定落在中间节点;当链表节点为偶数个时,最后快指针将落在最后一个节点上,所以只需要判断快指针的 next 节点为不为空即可

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* guard = malloc(sizeof(struct ListNode));
    guard->next = head;//定义哨兵位节点
struct ListNode* fast = guard;
struct ListNode* slow = guard;
while(fast)
{
    slow = slow->next;//慢指针一次走一步
    if(fast->next)
    {
    fast = fast->next->next;//快指针一次走两步
    }
    else
    {
        return slow;
    }
}
return slow;
}

~

今天就先到这里吧,摸了家人们。

有关单手杀穿经典链表题Pt.1——LeetCode天梯渡劫(移除节点,反转链表,中间节点)的更多相关文章

  1. Python 刷Leetcode题库,顺带学英语单词(31) - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. 区块链入门教程(6)--WeBASE-Front节点前置服务安装 - 2

    文章目录1.任务背景2.任务目标3.相关知识点4.任务实操4.1安装配置JDK4.2启动FISCOBCOS4.3下载解压WeBASE-Front4.4拷贝sdk证书文件4.5启动节点4.6访问节点4.7检查运行状态5.任务总结1.任务背景FISCOBCOS其实是有控制台管理工具,用来对区块链系统进行各种管理操作。但是对于初学者来说,还是可视化界面更友好,本节就来介绍WeBASE管理平台,这是一款微众银行开源的自研区块链中间件平台,可以降低区块链使用的门槛,大幅提高区块链应用的开发效率。微众银行是腾讯牵头设立的民营银行,在国内民营银行里还是比较出名的。微众银行参与FISCOBCOS生态建设,一定

  3. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码,在LeetCode上刷题时,如果能够在IDEA编写代码,并且做好代码管理,是一件事半功倍的事情。对于后续复习题目,做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用,以及配置工具类,最终目录结构如下:note:放置笔记src:放置代码leetcode.editor.cn:插件LeetCodeEditor自动生成utils:自定义的工具包,可用于自动化输入测试用例,定义题目需要的类(结构体)out:运行测试时自动生成LeetCodeEditorGitHub:https://github.com/shuzijun/leetcode-edit

  4. ruby - 选择包含子节点内文本的父节点 - 2

    基本上我想选择一个节点(div),其中它的子节点(h1,b,h3)包含指定的文本。Childtext1Childtext2...Childtext3我期待的是/html/div/而不是/html/div/h1我在下面有这个,但不幸的是返回了child,而不是div的xpath。expression="//div[contains(text(),'Childtext1')]"doc.xpath(expression)我期待的是/html/div/而不是/html/div/h1那么有没有一种方法可以简单地使用xpath语法来做到这一点? 最佳答案

  5. ruby - 如何在数组中间插入一个数组? - 2

    我有一个Ruby数组[1,4]。我想在中间插入另一个数组[2,3],这样它就变成了[1,2,3,4]。我可以使用[1,4].insert(1,[2,3]).flatten实现这一点,但是有更好的方法吗? 最佳答案 您可以通过以下方式进行。[1,4].insert(1,*[2,3])insert()方法处理多个参数。因此,您可以使用splat运算符*将数组转换为参数。 关于ruby-如何在数组中间插入一个数组?,我们在StackOverflow上找到一个类似的问题:

  6. ruby-on-rails - 如何在关闭 cache_classes 的情况下使用来自中间件的域对象? - 2

    在rails开发环境中,cache_classes是关闭的,所以你可以修改app/下的代码,不用重启服务器就可以看到变化。不过,在所有环境中,中间件只会创建一次。所以如果我有这样的中间件:classMyMiddlewaredefinitialize(app)@app=appenddefcall(env)env['model']=MyModel.firstendend我在config/environments/development.rb中执行此操作:config.cache_classes=false#thedefaultfordevelopmentconfig.middleware.

  7. ruby-on-rails - 保存 PDFKit 中间件显示的 PDF 文件 - 2

    如果有人有兴趣将PDF文件保存在PDFKit中间件gem显示的文件系统中,那么这里是...重写middleware.rb文件的call方法。在覆盖中只需替换这一行:body=PDFKit.new(translate_paths(body,env),@options).to_pdf与pdf=PDFKit.new(translate_paths(body,env),@options)file=pdf.to_file('Your/file/name/path')Mymodel.my_method()#Youcanwriteyourmethodheretousethatfilebody=pdf

  8. ruby - 删除指定节点之后的所有节点 - 2

    这个问题在这里已经有了答案:Nokogiri:SelectcontentbetweenelementAandB(3个答案)关闭2年前。我正在从url中抓取文本的div,并想删除具有backtotop类的段落下方的所有内容。我在stackoverflow上看到了一段遍历代码片段,看起来很有希望,但我不知道如何将它合并,所以@el只包含第一个p.backtotop之前的所有内容分区我的代码:@doc=Nokogiri::HTML(open(url))@el=@doc.css("div")[0]end遍历片段:doc=Nokogiri::HTML(code)stop_node=doc.css

  9. ruby-on-rails - Rack 中间件和线程安全 - 2

    我的Rails4应用程序使用了一个自定义Rack中间件。如果客户端未提供有效信息(我'正在开发API)。因此,在每个请求之前它会更改这些header,并且在每个请求之后它会添加一个带有自定义媒体类型信息的自定义X-Something-Media-Typeheader。我想切换到Puma,因此我有点担心这种中间件的线程安全性。我没有使用实例变量,除了我们在每个中间件中遇到的常见@app.call一次,但即使在这里我也复制了一些我在RailsCasts的评论中读到的内容:definitialize(app)@app=appenddefcall(env)dup._call(env)endde

  10. ruby-on-rails - rails delete_if 使用哈希忽略当前文章(中间人) - 2

    我为你们准备了一个简单的。我想要一个特色内容部分,其中排除了当前文章所以这可以通过delete_if使用MiddlemanBlog:但是我使用的是中间人代理,所以我无法访问current_article方法...我有一个YAML结构,其中包含以下模拟数据(以及其他数据),文件夹设置如下:data>site>caseStudy>RANDOM-ID423536.yaml(由CMS生成)在每个yaml文件中,您会发现如下内容::id:2k1YccJrQsKE2siSO6o6ac:title:Heyplace我的config.rb看起来像这样data.site.caseStudy.eachdo

随机推荐