Java链表的天然递归结构性质图文与实例分析

本文实例分析了Java链表的天然递归结构性质。分享给大家供大家参考，具体如下：

有关链表，参考之前的文章学习。

要求：使用递归删除链表中指定的所有元素值。

一、图文分析

假设有这么一个链表，如下图：

分析：基于链表的宏观语意（递归是问题更小的子过程）进行分析

我们可以把上述链表看成是一个头结点后面挂接了一个更小的链表组成，如下图：

此时我们可以把链表概括成如下的链表结构：

1、在一个头结点+更小的链表基础上，从更小的链表中删除指定元素，得到一个全新的链表--图中红丝的方块。

此时我们需要关心如何根据红丝的方块代码的链表构建出原问题的解-------也就是包括了原来头结点(头结点e)在内的情况。

2.判断头结点e是否是需要被删除的元素值，若头结点是不需要被删除的，此时的链表结构为头结点e+红色方块，否则为红色方块，相关结构图如下：

二、代码实现

package LeetCodeSubject;
/*
 * 使用虚拟头节点
 * */

class Solution3 {

  public ListNode removeElements(ListNode head, int val) {

    if (head == null)
      return null;

    ListNode res = removeElements(head.next, val);

    if (head.val == val)
      return res;
    else {
      head.next = res;
      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 Solution()).removeElements(head, 6);
    System.out.println(res);

  }
}

结果如下：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

赞 (0)

相关推荐

  • Java实现链表中元素的获取、查询和修改方法详解

    本文实例讲述了Java实现链表中元素的获取.查询和修改方法.分享给大家供大家参考,具体如下: 本节是在上一小节Java链表中添加元素的基础上继续完善我们的链表相关方法的编写,在本节中我们着重对如何获取链表中元素.查询元素以及修改元素进行学习. 一.获取元素 1.关于获取链表中元素的方法的分析 由于我们使用了虚拟头结点,而我们每次都需要从第一个真实节点开始,因此需要首先得到虚拟头结点的下一个节点是谁,然后在此基础上进行遍历工作,相关代码如下: //获取链表的第index(0-based)个位置的元

  • Java链表中添加元素的原理与实现方法详解

    本文实例讲述了Java链表中添加元素的原理与实现方法.分享给大家供大家参考,具体如下: 1.链表中头节点的引入 1.1基本的链表结构: 1.2对于链表来说,若想访问链表中每个节点则需要把链表的头存起来,假如链表的头节点为head,指向链表中第一个节点,如图: 1.3使用代码表示此时的链表 //定义头节点 private Node head; //节点个数 private int size; //无参数构造函数 public LinkedList() { head = null; size = 0

  • Java链表中元素删除的实现方法详解【只删除一个元素情况】

    本文实例讲述了Java链表中元素删除的实现方法.分享给大家供大家参考,具体如下: 该部分与上一节是息息相关的,关于如何在链表中删除元素,我们一步一步来分析: 一.图示删除逻辑 假设我们需要在链表中删除索引为2位置的元素,此时链表结构为: 若要删除索引为2位置的元素,需要获取索引为2位置的元素之前的前置节点(此时为索引为1的位置的元素),因此我们需要设计一个变量prev来记录前置节点. 1.初始时变量prev指向虚拟头结点dummyHead: 2.寻找到前置节点位置,(对于该例子前置节点为索引为1

  • Java基于链表实现栈的方法详解

    本文实例讲述了Java基于链表实现栈的方法.分享给大家供大家参考,具体如下: 在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳 在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1),基于链表的这几个优势,我们在此基础上实现栈. 前言,在写本小节之前,我们已经实现了一个基于静态数组的栈,转到查看.此处我们实现基于链表的栈. 1.链表类拷贝到Stack 包下: 在实现基于静态数组的栈的时候,我们已经新建了

  • Java递归基础与递归的宏观语意实例分析

    本文实例讲述了Java递归基础与递归的宏观语意.分享给大家供大家参考,具体如下: 1.什么是递归 本质上,将原来的问题,转化为更小的同一问题 2.例子分析 假设我们需要对数组进行求和操作(只是为了更好理解递归程序) 要求如下:求解从索引为0到n-1的数组元素和. 分析: 为了能求解从索引为0到n-1的数组元素和,可以分解为第0个数加上索引从1到n-1的数组元素和,如下: 此时求解索引从1到n-1的数组元素和的规模比求解从索引为0到n-1的数组元素和要少一个数以此类推,如下: ....... 最基

  • java链表应用--基于链表实现队列详解（尾指针操作）

    本文实例讲述了java基于链表实现队列.分享给大家供大家参考,具体如下: 在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1). 一.链表改进分析 对于队列这种数据结构,需要在线性结构的一端插入元素,另外一端删除元素.因此此时基于链表来实现队列,则有一端的时间复杂度为O(n).因此我们不能使用之前已经实现的链表结构,我们需要改进我们的链表.思路如下: 1.参考在链表头部删除.增加元素的时间复杂度为O(1)的思路,我们在链表的尾部设立一个Node型的

  • java递归算法的实例详解

    递归三要素: 1.明确递归终止条件: 2.给出递归终止时的处理办法: 3.提取重复的逻辑,缩小问题规模. 1.1+2+3+-+n import java.util.Scanner; public class Recursion { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(sum(n)); } publ

  • Java递归运行的机制：递归的微观解读图文分析

    本文讲述了Java递归运行的机制:递归的微观解.分享给大家供大家参考,具体如下: 前言:在java递归基础与递归的宏观语意和java链表的天然递归结构性质中我们分别通过数组以及链表对递归进行了应用,那时我们只是对递归进行了宏观理解--递归是将问题化为更小问题的子过程.这一节我们对在4.1节中递归在数组中的应用和4.2节中递归在链表中的应用进行微观解读: 一.关于4.1节中递归在数组中的应用 1) 我们先来看看4.1节中的代码实现,如下图: 为了更好的进行分析,我们将上述代码的最后一句进行拆分,拆

  • Java链表（Linked List）基本原理与实现方法入门示例

    本文实例讲述了Java链表(Linked List)基本原理与实现方法.分享给大家供大家参考,具体如下: 在分析链表之前,我们先来对之前的动态数组.栈.队列总结一下: (1)底层依托于静态数组 (2)依靠resize解决固定容量问题 (3)是一种假的的动态数据结构 1.什么是链表 可以从以下两个部分来理解什么是链表 (1)最简单的动态数据结构,是一种真正的动态数据结构: (2)是一种数据的存储方式,数据存储在"节点"(Node)中 1.1结构基本代码: class Node{ E e;

  • Java方法递归调用实例解析

    Java方法递归调用实例解析

    这篇文章主要介绍了Java方法递归调用实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /* 关于方法的递归调用 1.什么是递归? -方法自身调用自身 a(){ a(){ } } 2.递归是很耗费栈内存的,递归算法可以不用的时候尽量不用 3.一下程序运行的时候发生了这样一个错误[不是异常,是错误Error]: java.lang.StackOverflowErroe 栈内存溢出错误. 错误放生无法挽回,只有一个结果,就是JVM停止工作 4

  • 如何实现java递归 处理权限管理菜单树或分类

    如何实现java递归 处理权限管理菜单树或分类

    这篇文章主要介绍了如何实现java递归 处理权限管理菜单树或分类,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.数据库表设计 2.实体类设计 package com.ieou.capsule.dto.SystemPermissions; import java.util.List; /** * 功能菜单类 */ public class SystemPermissionsTree { private String functionCode;

随机推荐