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。

相关文章

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“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-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
如何恢复回收站中已删除/清空的文件

如何恢复回收站中已删除/清空的文件

回收站清空后如何恢复已删除的文件？是否可以恢复永久删除的文件？或者最糟糕的是，如果文件直接被删除怎么办？本文将向您展示清空回收站后恢复已删除数据的最佳方法。 回收站清空后如何恢复已删除的文件？ “回收站清空后我还能恢复已删除的文件吗？” 答案是肯定的，但是在这种情况下您将需要一个  回收站恢复工具 来从回收站中检索文件： 错误/永久删除回收站或任何数字存储设备中的文件 直接删除的文件/
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
(function() {})();只执行一次

(function() {})();只执行一次

测试例子： var xx = (function() {     (function() { alert(9) })(); alert(10)     return "yyyy";  })(); 调用： alert(xx); 在调用的时候，你会发现只弹出"yyyy"信息，并不见弹出"10"的信息！这也就是说，这个匿名函数只在立即调用的时候执行一次，这时它已经赋予了给xx变量，也就是只是
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2