第5章：链表和递归密不可分的关系(Leetcode原题)

2024-02-25 17:59
文章标签 leetcode 链表 关系 递归 原题 密不可分

本文主要是介绍第5章：链表和递归密不可分的关系(Leetcode原题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第五章 链表和递归

5-1 Leetcode中和链表相关的问题
5-2 测试自己的Leetcode链表代码
5-3 递归基础与递归的宏观语意
5-4 链表的天然递归结构性质
5-5 递归运行的机制：递归的微观解读
5-6 递归算法的调试
5-7 更多和链表相关的问题

5-1 Leetcode中和链表相关的问题
https://leetcode-cn.com/problems/remove-linked-list-elements/

题目中给出了ListNode的定义。接下来用两种方法进行链表中元素的删除：

//Definition for singly-linked list.
public class ListNode {public int val;public ListNode next;public ListNode(int x){val = x;}
}

解法一：没有虚拟头节点的情况
（1）删除头节点，可能需要连续删除，需要使用while循环（比如示例中有两个6需要删除）

ListNode delNode = head;
head = head.next;
delNode.next = null;

（2）删除中间的节点也需要使用while循环，循环条件是 prev.next != null; 删除条件是 prev.next.val == val.

ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;

注意元素删除后，不要立即将prev右移，因为可能新的prev.next也是需要删除的节点，这时候需要再次进入while循环。

class Solution1 {public ListNode removeElements(ListNode head, int val){while(head != null && head.val==val){// head = head.next; (下面三行代码可以简化为这一行代码)ListNode delNode = head;head = head.next;delNode.next = null;}if(head == null){return null;}ListNode prev = head;while(prev.next != null){if(prev.next.val == val){// prev.next = prev.next.next; (下面三行代码可以简化为这一行代码)ListNode delNode = prev.next;prev.next = delNode.next;delNode.next = null;}else{prev = prev.next;}}return head;}
}

解法二：使用虚拟节点dummyhead的情况
使用dunmmyHead需要注意链表是否为空（详细的说明可以查看4-5）

class Solution2 {public ListNode removeElements(ListNode head, int val){ListNode dummyHead = new ListNode(-1);dummyHead.next = head;ListNode prev = dummyHead;while(prev.next != null){if(prev.next.val == val){prev.next = prev.next.next;}else{prev = prev.next;}}return dummyHead.next;}
}

简单总结：

  • LeetCode上的原题，给定一个value让你删除其链表中所有相同值的节点，与上一个章节对链表的操作是完全相同的，唯一一点区别在于把if判断语句改成了while，是因为在一个链表中可能存在多个相同数值的节点。

5-2 测试上述Leetcode链表代码
通过一个数组构建一个链表 (使用arr为参数，创建一个链表，当前的ListNode为链表头节点)，并且打印这个链表相应的字符串。

 // 链表节点的构造函数// 使用arr为参数，创建一个链表，当前的ListNode为链表头节点public ListNode(int[] arr){if (arr == null || arr.length == 0)throw new IllegalArgumentException("arr cannot be empty");this.val = arr[0];ListNode cur = this;for (int i = 1; i < arr.length; i++){cur.next = new ListNode(arr[i]);cur = cur.next;}}// 以当前节点为头节点的链表信息字符串@Overridepublic String toString(){StringBuilder res = new StringBuilder();ListNode cur = this; // 从自身开始进行循环while(cur != null){res.append(cur.val + "->");cur = cur.next;}res.append("NULL");return res.toString();}

题目所给的测试用例的实现及结果如下：

 public static void main(String[] args){int[] nums = {1, 2, 6, 3, 4, 5, 6};ListNode head = new ListNode(nums);System.out.println(head);ListNode res = (new Solution1()).removeElements(head, 6);// ListNode res = (new Solution2()).removeElements(head, 6);System.out.println(res);}

1->2->6->3->4->5->6->NULL
1->2->3->4->5->NULL

5-3 递归基础与递归的宏观语义
递归：本质上，将原来的问题，转化为更小的同一问题

用代码来实现数组求和：

public class Sum {// 为用户设计使用的sum函数// 用户只需要传进来一个int型的arr数组public static int sum(int[] arr){return sum(arr, 0);// 0：递归的初始调用是从0到n-1这些元素所有的和}// 计算arr[l,...,n]这个区间内所有数字的和// 这个sum函数是真正的递归函数private static int sum(int[] arr, int l){if (l == arr.length)    return 0;return arr[l] + sum(arr, l+1);// 从计算[l,n]区间数字的和 -> 计算[l+1,n]区间数字的和}public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 6, 7, 8};System.out.println(sum(nums));}
}
  • 在写递归函数的时候，一定要注重递归函数本身的语义（递归函数的宏观语义）不用太纠结于里边具体的程序执行机制。本质上：函数A里边调用函数A，与函数A里边调用函数B是没有区别的。
  • 写递归算法的基本原则：第一个部分是求解最基本问题； 第二部分是把原问题转化成更小的问题。
  • 将一个问题分解成一个更小的问题，一个更小的问题再分解成一个更更小的问题…最后一直分解直至称为一个可以解决的最基本的问题，最基本的问题靠程序员自己编写逻辑求解。

举个栗子：在数组求和的这个例子中，待解决的问题是将数组中所有的数进行求和。将其分解为更小的一个问题就是从第一个元素求到最后一个元素的和，再分解为从第二个元素求到最后一个元素的和…这样分解直至只用求最后一个元素为止。那么求最后一个元素的值便是程序员所要解决的最基本的问题。

  • 把原问题转化为更小的问题不是简单地求一个更小的问题的答案，要根据更小的问题的答案构建出原问题的答案。（这里表现为arr[1] + 更小的数组中的元素的和）

对于一个复杂的递归算法来说，这个逻辑可能是非常复杂的。
难点在于如何把一个问题转化为一个更小的问题，并根据更小问题的答案构建出原问题的答案。

  1. 注意递归函数的“宏观”语义
  2. 递归函数就是一个函数，完成一个功能

5-4 链表的天然递归结构性质

对于这个链表可以想像成是0这个节点后边又挂了一个更短的链表（比整个链表少了一个节点），这里1就是这个更短链表的头节点，以此类推，直到最后可以理解为NULL本身也是一个链表，而NULL就是那个最基础、最平凡的链表。

解法三：用递归来解决链表中删除元素的问题：

代码实现如下：

public class Solution3 {// 使用递归方法来解决问题public ListNode removeElements (ListNode head, int val){if (head == null)return null;ListNode res = removeElements(head.next, val);// 宏观语义：对一个链表中删除值为val的节点// head后边接的那个更短的链表(head.next)，将这个链表中值为val相应的元素删除// res中存储的就是：将头节点后边跟的那个链表中所有的值为val的节点删除后，剩下的这个链表if (head.val == val)return res;else{head.next = res;return head;}}
}

这里注意一下可以简化以上代码，四行代码就可以完美解决这个问题。

 // 使用递归方法来解决问题public ListNode removeElements (ListNode head, int val){if (head == null)return null;head.next = removeElements(head.next, val);return head.val == val ? head.next : head;// 上一行代码可以解释为下面的代码：
//        if (head.val == val)
//            return head.next;
//        else{
//            return head;}}

运行一下这个代码，结果如下：

public static void main(String[] args){int[] nums = {1, 2, 6, 3, 4, 5, 6};ListNode head = new ListNode(nums);System.out.println(head);ListNode res = (new Solution3()).removeElements(head, 6);System.out.println(res);}

1->2->6->3->4->5->6->NULL
1->2->3->4->5->NULL

5-5 递归运行的机制：递归的微观解读

  • 递归函数的调用，本质就是函数调用，只不过调用的函数是自己而已。
    举个栗子：

  • 递归调用至最后一个子程序时，返回值会返回上一个子程序终止位置继续执行。

与程序调用系统栈原理一致。

  • 这里简单的表述一下：调用sum(arr, 2)，返回值为0 (if(l == n) return 0)，因此在调用sum(arr, 1)中，sum(arr, l+1)的值为0，因此，x=0, res = arr[1] + 0 = 10 (这里arr[1] = 10, x = 0)。上一步我们得到了调用sum(arr, 1)的返回值res = 10, 因此在sum(arr, 0)中，sum(arr, l+1)的值为10，因此x = 10, res = arr[0] + 10 = 16 (这里arr[0] = 6, x = 10)。最后我们得到的返回结果为：16

-> 用程序调用系统栈的方式进行一次解释：

  • 具体过程不再详细描述，可以自己先思考一下看是否能够理解。若不能理解，再次观看教学视频：
    https://coding.imooc.com/lesson/207.html#mid=13441
  • 递归的调用本质上和子过程的调用是没有区别的，A调用B，B调用C == A调用A，A调用A
  • 从代码的角度看，执行递归调用的本质是重新调用了以下逻辑，但此时是对一组新的参数调用了逻辑
  • 递归调用是有代价的： 函数调用 + 系统栈空间
  • 递归调用编写非线性数据结构（树结构、图结构）的代码逻辑更简单一些，线性结构由于结构简单使得递归调用的优势并不明显，使用常用的循环遍历即可解决大部分线性结构问题。

5-6 递归算法的调试
-> 使用一个打印输出的方式，来展现出一个递归函数调用的整个过程。

import java.util.List;public class Test {public ListNode removeElements(ListNode head, int val, int depth){String depthString = generateDepthString(depth);System.out.println(depthString);System.out.println("Call: remove " + val + " in " + head);if (head == null){System.out.println(depthString);System.out.println("Return: " + head);return head;}ListNode res = removeElements(head.next, val, depth+1);System.out.println(depthString);System.out.println("After remove" + val + ": " + res);ListNode ret;if (head.val == val)ret = res;else {head.next = res;ret = head;}System.out.println(depthString);System.out.println("Return: " + ret);return ret;}private String generateDepthString(int depth){StringBuilder res = new StringBuilder();for (int i = 0; i < depth; i ++)res.append("--");return res.toString();}public static void main(String[] args){int[] nums = {1, 2, 6, 3, 4, 5, 6};ListNode head = new ListNode(nums);System.out.println(head);ListNode res = (new Test()).removeElements(head, 6, 0);System.out.println(res);}
}

运行结果如下：

1->2->6->3->4->5->6->NULL
– Call: remove 6 in 1->2->6->3->4->5->6->NULL
---- Call: remove 6 in 2->6->3->4->5->6->NULL
------ Call: remove 6 in 6->3->4->5->6->NULL
-------- Call: remove 6 in 3->4->5->6->NULL
---------- Call: remove 6 in 4->5->6->NULL
------------ Call: remove 6 in 5->6->NULL
-------------- Call: remove 6 in 6->NULL
-------------- Call: remove 6 in null
------------ Return: null
------------ After remove6: null
---------- Return: null
---------- After remove6: null
-------- Return: 5->NULL
-------- After remove6: 5->NULL
------ Return: 4->5->NULL
------ After remove6: 4->5->NULL
---- Return: 3->4->5->NULL
---- After remove6: 3->4->5->NULL
– Return: 3->4->5->NULL
– After remove6: 3->4->5->NULL
Return: 2->3->4->5->NULL
After remove6: 2->3->4->5->NULL
Return: 1->2->3->4->5->NULL
1->2->3->4->5->NULL

5-7 更多和链表相关的问题

  • 近乎和链表相关的所有操作，都可以使用递归的形式完成
  • 建议同学们对链表的增、删、改、查，进行递归实现
  • Leetcode中链表/递归相关的题目可以看看（不要想着把所有的问题都解决了再进行下面的学习）
  • 双链表、循环链表、数组链表

这篇关于第5章：链表和递归密不可分的关系(Leetcode原题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/746257。

相关文章

Tomcat版本与Java版本的关系及说明

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》：本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ
阅读更多...
Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR
阅读更多...
python安装whl包并解决依赖关系的实现

python安装whl包并解决依赖关系的实现

《python安装whl包并解决依赖关系的实现》本文主要介绍了python安装whl包并解决依赖关系的实现,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录一、什么是whl文件？二、我们为什么需要使用whl文件来安装python库？三、我们应该去哪儿下
阅读更多...
Rust中的BoxT之堆上的数据与递归类型详解

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
MYSQL关联关系查询方式

MYSQL关联关系查询方式

《MYSQL关联关系查询方式》文章详细介绍了MySQL中如何使用内连接和左外连接进行表的关联查询,并展示了如何选择列和使用别名,文章还提供了一些关于查询优化的建议,并鼓励读者参考和支持脚本之家... 目录mysql关联关系查询关联关系查询这个查询做了以下几件事MySQL自关联查询总结MYSQL关联关系查询
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
POJ1269 判断2条直线的位置关系

POJ1269 判断2条直线的位置关系

题目大意：给两个点能够确定一条直线，题目给出两条直线（由4个点确定），要求判断出这两条直线的关系：平行，同线，相交。如果相交还要求出交点坐标。 解题思路： 先判断两条直线p1p2, q1q2是否共线， 如果不是，再判断 直线 是否平行， 如果还不是， 则两直线相交。  判断共线：  p1p2q1 共线 且 p1p2q2 共线 ，共线用叉乘为 0  来判断，  判断 平行：  p1p
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2