专栏首页golang小白成长记链表问题,如何优雅递龟?

链表问题,如何优雅递龟?

关注下方名片,即可获取算法编程语言力扣刷题手册等海量资料!

前言

大家好,我是来自华为的「程序员小熊」。相信绝大部分童鞋都知道,在处理与「链表」相关问题时,常用的解题套路主要包括「双指针」「迭代」「虚拟头节点」等等。

今天「小熊」主要介绍采用「递归」的策略,秒杀「链表」相关问题,使得代码更「优雅」,并以两道常见的面试题作为例题来讲解,供大家参考,希望对大家有所帮助。

链表与递归

链表具有天然的递归性,一个链表可以看出头节点后面挂接一个更短的链表,这个更短的链表是以原链表的头节点的下一节点为头节点,依次内推,直到最后的更短的链表为空,空本身也是一个链表(最基础的)。

以单链表 1->2->3->null 为例子,如下图示:

原链表

将原链表看出头节点 1 后挂接一个更短的链表

头节点+更短链表

继续拆解,直到无法拆解

更更短链表

更更更短链表

有了这样的思考,很多「链表」相关问题,都可以采用「递归」的思路来解答。

剑指 Offer 24. 反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
 

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
 

限制:
0 <= 节点个数 <= 5000

解题思路

要反转链表,即将原链表的头节点变为新链表的尾节点,原链表的尾节点变为新链表的头节点。如下图示:

反转之前:

原链表

反转之后:

新链表

主要策略主要有:1、直接修改链表的值,如上图中的原链表图所示,将原链表值 1 的头节点改为原链表尾节点的值,依次类推;2、让遍历整个链表,让链表的尾节点指向其前一个节点,依次类推。

虽然这两个策略都可行,不过在面试中通常要求采用「策略2」

由上面的「递归与链表」可知,本题也可以采用「递归法」去求解。

具体如何通过「递归」去解答呢?见下面例子。

「举例」

链表 1->2->3->null 为例子,如下图示。

示例

不断遍历找到原链表为尾节点,即新链表的头节点。

原链表尾节点

然后让尾节点指向其前驱节点,依次类推。

递归反转

详细步骤,如下动图示:

递归反转单链表

Show me the Code

「C」

struct ListNode* reverseList(struct ListNode* head){
    /* 递归终止条件 */
    if (head == NULL || head->next == NULL) {
        return head;
    }

    /* 反转当前所在的链表节点 */
    struct ListNode* newHead = reverseList(head->next);

    /* 由原链表的尾节点挨个指向其前驱节点 */
    head->next->next = head;

    /* 防止成环 */
    head->next = NULL;

    /* 返回新的链表头节点 */
    return newHead;
}

「java」

ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode node = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return node;
}

当然本题也可以采用「迭代」的方法去做,其代码(python 版)也很优雅,具体如下:

Show me the Code

「python」

def reverseList(self, head: ListNode) -> ListNode:
    cur, pre = head, None
    while cur:
        cur.next, pre, cur = pre, cur, cur.next
        
    return pre 

「复杂度分析」

时间复杂度:「O(n)」,n 是链表的长度。对链表的每个节点都进行了反转操作。

空间复杂度:「O(n)」,n 是链表的长度。递归调用的栈空间,最多为 n 层。

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 

Node.val == val 的节点,并返回 新的头节点 。

示例 1:

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

示例 2:

输入:head = [], val = 1
输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]

解题思路

要移除链表中给定值的节点,一般策略是「找到给点值的节点的前驱节点,然后让其指向给定值的节点的后继节点」

例如要删除链表 1->2->3->null 中,节点值为 3 的节点,就得先找到其前驱节点(值为 2 的节点),如下图示:

删除给定值的节点

由上面的「递归与链表」可知,本题同样也可以采用「递归法」去求解,不断删除更短链表中给定值的节点,然后再将处理后的更短的链表,挂接在其前驱节点后。

「注意」最后要判断原链表的头节点是否是待移除的节点。

「举例」

以链表 1->2->3->null 为例子,移除链表中给定值的节点的过程,如下动图示。

示例动图

Show me the Code

「C++」

ListNode* removeElements(ListNode* head, int val) {
    /* 递归终止条件 */
    if(head == NULL) {
        return NULL;
    }

    /* 删除链表中头节点后值为 val 的元素的节点 */
    head->next=removeElements(head->next,val);

    /* 判断头节点是否为值为 val 的节点,再返回*/
    return head->val==val ? head->next : head;
}

「Golang」

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }

    head.Next = removeElements(head.Next, val)
    if head.Val == val {
        return head.Next
    }

    return head
}

「复杂度分析」

时间复杂度:「O(n)」,n 是链表的长度。递归需要遍历链表一次。

空间复杂度:「O(n)」,n 是链表的长度。递归调用栈,最多不会超过 n 层。

本文分享自微信公众号 - golang小白成长记(golangxbczj)

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

原始发表时间:2021-06-09

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表问题,如何优雅递龟?

    大家好,我是来自「华为」的「程序员小熊」。绝大部分童鞋都知道,解决「链表」相关问题时,常用的解题套路主要包括「双指针」、「迭代」和「虚拟头节点」等等。

    程序员小熊
  • 链表问题,如何优雅递龟吗?

    大家好,我是来自华为的「程序员小熊」。相信绝大部分童鞋都知道,在处理与「链表」相关问题时,常用的解题套路主要包括「双指针」、「迭代」和「虚拟头节点」等等。

    程序员小熊
  • 如何有效的写算法题

    “龟系”刷法的精髓就是每个题目都做干净。不满足于一种解法,各种解法都写一写。这种流派适合不太急于准备算法面试的小伙伴,追求算法的干净优雅。

    五分钟学算法
  • 你不可不会的几种移动零的方法(续集)

    大家好,我是「程序员小熊」,就职于「华为」。在上期 你不可不会的几种移动零的方法 中,小熊主要介绍了「末尾补零」和「交换零元素与非零元素」两种方法解答力扣第28...

    程序员小熊
  • 【链表问题】打卡6:三种方法带你优雅判断回文链表

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • Js算法与数据结构拾萃(3):链表

    对于一个数组,想要做篡改是复杂度是非常高的,设想你接到一个需求,让你记录存储一个人的简历,你用数组储存,可能是这样的:

    一粒小麦
  • 如何优雅的解决群友的Python问题?

    这个问题来源于自己Python交流群中的一个问题,如下图所示,需要计算每列中各值的出现次数,然后组成一个新的表。

    罗罗攀
  • Java 是如何优雅地处理NPE问题的

    对于 Java 开发者来说,null 是一个令人头疼的类型,一不小心就会发生 NPE (空指针) 问题。也是 Java 语言为人诟病的一个重要原因之一。在我们消...

    码农小胖哥
  • 零基础学编程025:前24课总结

    学会如何学习 2016年12月21日,写下了“零基础学编程”的首篇文章:“零基础学编程”都需要哪些基础?计算机都是从0开始计数,所以就叫第0篇文章了。学习任何技...

    申龙斌
  • 01.入门~Python前世今身

    说起Python的由来,那是1989年的圣诞节的夜晚,龟叔(Guido van Rossn)由于孩子教育的原因和妻子吵架,一个人独守客厅中的壁炉,无聊之中突发臆...

    大牧莫邪
  • 聊一聊如何优雅地向程序员提问题

    木东居士
  • 带你学python基础:彻彻底底的入门

    在我们学习这门语言之前,我们还是先来了解了解这门语言的历史,比如说,其他的语言,像c、c++、Java等,在学习之前,或多或少的我们还是了解了一些这门语言的来龙...

    好好学java
  • Python从入门到大师一百篇教程 | 前言:Python的前世和发展

    本文是Python从入门到大师共100教程前言篇,系列文章教程已经在CSDN完结,公众号每日一更。

    润森
  • 在编程中发现数学之美——使用Python小龟绘制多边形

    在使用数学知识画出很酷的各种图形之前,你需要先学习Python编程语言的基础知识。本文将会带你熟悉以下编程概念:循环、变量、函数、使用小龟模块绘制图像。本文假设...

    fanzhh
  • 校招面试手撕算法汇总

    所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

    牛客网
  • LeetCode,给定一个链表,判断链表中是否有环

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索...

    微客鸟窝
  • CSS前端基础

    Albert_xiong
  • Python3 系列(一):HelloWorld

    Python是著名的“龟叔”Guido van Rossum在1989年圣诞节期间,为了打发无聊的圣诞节而编写的一个编程语言。龟叔给Python的定位是“优雅”...

    山禾说
  • 数据结构基础-链表

    数组一样能用来存储数据集合,那为什么用多种数据结构来做一样的事情。因为后来发现数组在处理一些情况下的弊端,所以开始分使用情景用不同的工具干同样的事情。 先说说...

    1025645

扫码关注云+社区

领取腾讯云代金券