3.4 从无头链表中删除给定的结点 遍历一次逆转链表

2024-05-28 15:58
文章标签 遍历 3.4 链表 删除 一次 结点 给定 逆转 无头

本文主要是介绍3.4 从无头链表中删除给定的结点 遍历一次逆转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 前言

本文的一些图片, 资料 截取自编程之美

2. 问题描述

这里写图片描述
这里写图片描述

3. 问题分析

第一个问题 : 因为给出的只是一个链表的结点, 来删除当前结点, 所以想要找出当前结点的前一个结点貌似不可能, 所以只有另想一种方法了
这里的方法是 : “狸猫换太子”, 将下一个元素的数据复制到当前结点上面, 然后在删除下一个元素, 已达到”删除当前结点”的目的

第二个问题 : 记录下当前结点的下一个结点的下一个结点, 然后在更新下一个结点到当前结点的引用, 在更新当前结点的引用, 继续迭代，
可以有循环和递归两种处理方法, 但是最后一定要注意更新链表的头结点

4. 代码

/*** file name : Test06DelFromNoneHeadPointerLinkedList.java* created at : 9:16:16 AM May 28, 2015* created by 970655147*/package com.hx.test04;public class Test06DelFromNoneHeadPointerLinkedList {// 目的 给定一个单链表的一个指针, 然后移除该单链表的该指针处的值// 反转链表public static void main(String []args) {LinkedList ll = new LinkedList();
//      LinkedList02 ll = new LinkedList02();ll.add(4);ll.addLast(2);ll.addFirst(5);ll.addLast(34);ll.addFirst(51);Log.log(ll);Node cur = ll.head;cur = cur.next;cur = cur.next;Log.log(cur.data);delFromNoneHeadPointerLinkedList01(cur);Log.log(ll);//      reverseHeadPointerLinkedList01(ll.head);reverseHeadPointerLinkedList02(ll.head);Log.log(ll);}// 思路 : 将cur.next结点的元素复制给cur结点的元素  然后删除掉cur.next结点即可public static void delFromNoneHeadPointerLinkedList01(Node cur) {if(cur == null) {return ;}if(cur.next != null) {Node next = cur.next.next;cur.data = cur.next.data;cur.next = next;} else {Log.log("input Ref is tail node..");}}// 给出头结点 实现便利一次  反转链表// 先置空第一个结点[不是头结点].next  然后在利用next, nNext两个变量反转链表// 中间过程用到了tmp 一个临时变量[指向nNext.next  用于更新nNext]// 最后 更新head.next 为next结点public static void reverseHeadPointerLinkedList01(Node head) {if(head == null) {return ;}Node next = head.next, nNext = next.next;next.next = null;while (nNext != null) {Node tmp = nNext.next;nNext.next = next;next = nNext;nNext = tmp;} head.next = next;}// 反转链表  递归实现public static void reverseHeadPointerLinkedList02(Node head) {if(head == null) {return ;}if(head.next != null && head.next.next != null) {Node cur = head.next.next;head.next.next = null;recurselyReverseList(head.next, cur, cur.next, head);}}// 将cur.next指向prev之后   更新prev, cur, next 递归     知道cur为null   表示反转完毕private static void recurselyReverseList(Node prev, Node cur, Node next, Node head) {if(cur == null) {head.next = prev;return ;}cur.next = prev;prev = cur;cur = next;if(next != null) {next = next.next;} else {next = null;}recurselyReverseList(prev, cur, next, head);}// 单向链表的实现 [存在默认头结点]// 从实现需要考虑的方面  来说没有默认的头结点需要考虑头尾问题// 而存在默认头结点  则不太需要, 不明白为什么LinkedList为什么要采用后者,,,public static class LinkedList {Node head;Node tail;int size;public LinkedList() {head = new Node(-1, null);tail = head;size = 0;}public Node first() {return head.next;}// 添加一个元素到链表末尾public void add(int ele) {Node newNode = new Node(ele, null);tail.next = newNode;tail = newNode;size ++;}public void addNode(Node node) {tail.next = node;tail = tail.next;size ++;}// 添加一个元素到链表头public void addFirst(int ele) {add(0, ele);}// 添加一个元素到链表末尾public void addLast(int ele) {add(ele);}// 添加一个元素到链表指定索引处public void add(int idx, int ele) {Node pred = head, next = null;for(int i=0; i<idx; i++) {pred = pred.next;}next = pred.next;Node newNode = new Node(ele, next);pred.next = newNode;if(idx == size) {tail = tail.next;}size ++;}// 移除指定索引的链表元素public void remove(int idx) {Node pred = head, next = null;for(int i=0; i<idx; i++) {pred = pred.next;}next = pred.next.next;// 处理删除尾节点if(pred.next == tail) {tail = pred;}pred.next = next;size --;}// 移除值为指定值的链表元素public void removeForValue(int val) {Node pred = head, next = null;while(pred.next != null && pred.next.data != val) {pred = pred.next;}if(pred != null) {// 处理删除尾节点if(pred.next == tail) {tail = pred;}next = pred.next.next;pred.next = next;size --;}}// 获取指定索引的链表元素public int get(int idx) {Node pred = head.next;for(int i=0; i<idx; i++) {pred = pred.next;}return pred.data;}// 获取指定值的索引public int[] indexOf(int val) {Node pred = head;int idx = 0;int[] res = new int[0];while((pred = pred.next) != null ) {if(pred.data == val) {int[] newRes = new int[res.length + 1];System.arraycopy(res, 0, newRes, 0, res.length);newRes[newRes.length - 1] = idx;res = newRes;}idx ++;}return res;}// Debugpublic String toString() {StringBuilder sb = new StringBuilder(size << 3);Node cur = head;while((cur = cur.next) != null) {sb.append(cur.data + " -> ");}return sb.substring(0, sb.length() - 4);}}// 单向链表的实现 [不存在存在默认头结点]static class LinkedList02 {Node head;Node tail;int size;public LinkedList02() {head = tail = null;size = 0;}// 添加一个元素到链表末尾public void add(int ele) {Node newNode = new Node(ele, null);if(size == 0) {head = tail = newNode;} else {tail.next = newNode;tail = newNode;}size ++;}// 添加一个元素到链表头public void addFirst(int ele) {add(0, ele);}// 添加一个元素到链表末尾public void addLast(int ele) {add(ele);}// 添加一个元素到链表指定索引处public void add(int idx, int ele) {if(idx == 0) {if(size == 0) {Node newNode = new Node(ele, null);head = tail = newNode;} else {Node newNode = new Node(ele, head);head = newNode;}return ;}Node pred = head, next = null;for(int i=1; i<idx; i++) {pred = pred.next;}next = pred.next;           Node newNode = new Node(ele, next);pred.next = newNode;if(pred == tail) {tail = tail.next;}size ++;}// 移除指定索引的链表元素public void remove(int idx) {if(idx == 0) {head.data = 0;head = head.next;// 链表只有一个元素的情况下if(size == 1) {tail = head;}size --;return ;}Node pred = head, next = null;for(int i=1; i<idx; i++) {pred = pred.next;}next = pred.next.next;pred.next = next;size --;}// 移除值为指定值的链表元素public void removeForValue(int val) {Node pred = head, next = null;if(pred.data == val) {remove(0);}while(pred.next != null && pred.next.data != val) {pred = pred.next;}if(pred != null) {next = pred.next.next;pred.next = next;size --;}}// 获取指定索引的链表元素public int get(int idx) {Node pred = head;for(int i=0; i<idx; i++) {pred = pred.next;}return pred.data;}// 获取指定值的索引public int[] indexOf(int val) {Node pred = head;int idx = 0;int[] res = new int[0];while(pred != null ) {if(pred.data == val) {int[] newRes = new int[res.length + 1];System.arraycopy(res, 0, newRes, 0, res.length);newRes[newRes.length - 1] = idx;res = newRes;}pred = pred.next;idx ++;}return res;}// Debugpublic String toString() {StringBuilder sb = new StringBuilder(size << 3);Node cur = head;while(cur != null) {sb.append(cur.data + " -> ");cur = cur.next;}return sb.substring(0, sb.length() - 4);}}// 结点元素public static class Node {int data;Node next;String buildTime;// 初始化public Node() {super();this.buildTime = new Date().toString();}public Node(int data, Node next) {this();this.data = data;this.next = next;}// setter & getterpublic int getData() {return data;}public void setNext(Node next) {this.next = next;}public Node getNext() {return this.next;}// for debug ...public String toString() {return data + buildTime;}}}

5. 运行结果

这里写图片描述

6. 总结

第一个问题的解法比较巧妙, 将当前结点改头换面了, 然后将删除当前结点的任务改成了删除当前结点的下一个结点

注 : 因为作者的水平有限，必然可能出现一些bug, 所以请大家指出！

这篇关于3.4 从无头链表中删除给定的结点 遍历一次逆转链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Java实现删除文件中的指定内容

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja
阅读更多...
MySQL存储过程之循环遍历查询的结果集详解

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》：本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题：在生产上导入的数据发现
阅读更多...
Redis过期删除机制与内存淘汰策略的解析指南

Redis过期删除机制与内存淘汰策略的解析指南

《Redis过期删除机制与内存淘汰策略的解析指南》在使用Redis构建缓存系统时,很多开发者只设置了EXPIRE但却忽略了背后Redis的过期删除机制与内存淘汰策略,下面小编就来和大家详细介绍一下... 目录1、简述2、Redis http://www.chinasem.cn的过期删除策略（Key Expir
阅读更多...
Linux链表操作方式

Linux链表操作方式

《Linux链表操作方式》：本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与
阅读更多...
使用C#删除Excel表格中的重复行数据的代码详解

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元
阅读更多...
python进行while遍历的常见错误解析

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三
阅读更多...
Python对PDF书签进行添加,修改提取和删除操作

Python对PDF书签进行添加,修改提取和删除操作

《Python对PDF书签进行添加,修改提取和删除操作》PDF书签是PDF文件中的导航工具,通常包含一个标题和一个跳转位置,本教程将详细介绍如何使用Python对PDF文件中的书签进行操作... 目录简介使用工具python 向 PDF 添加书签添加书签添加嵌套书签Python 修改 PDF 书签Pytho
阅读更多...
C#实现查找并删除PDF中的空白页面

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删
阅读更多...
SQL常用操作精华之复制表、跨库查询、删除重复数据

SQL常用操作精华之复制表、跨库查询、删除重复数据

《SQL常用操作精华之复制表、跨库查询、删除重复数据》：本文主要介绍SQL常用操作精华之复制表、跨库查询、删除重复数据,这些SQL操作涵盖了数据库开发中最常用的技术点,包括表操作、数据查询、数据管... 目录SQL常用操作精华总结表结构与数据操作高级查询技巧SQL常用操作精华总结表结构与数据操作复制表结
阅读更多...
Java遍历HashMap的6种常见方式

Java遍历HashMap的6种常见方式

《Java遍历HashMap的6种常见方式》这篇文章主要给大家介绍了关于Java遍历HashMap的6种常见方式,方法包括使用keySet()、entrySet()、forEach()、迭代器以及分别... 目录1，使用 keySet() 遍历键，再通过键获取值2，使用 entrySet() 遍历键值对3，
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2