网站建设服务费应该算什么科目,做网站用什,四川建设网app,两屏合一网站建设#x1f525;博客主页#xff1a; 小扳_-CSDN博客 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 单链表的反转说明 2.0 单链表的创建 3.0 实现单链表反转的五种方法 3.1 实现单链表反转 - 循环复制#xff08;迭代法#xff09; 3.2 实现单链表反转 - 头插法 3… 博客主页 小扳_-CSDN博客 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 单链表的反转说明 2.0 单链表的创建 3.0 实现单链表反转的五种方法 3.1 实现单链表反转 - 循环复制迭代法 3.2 实现单链表反转 - 头插法 3.3 实现单链表反转 - 递归法 3.4 实现单链表反转 - 三指针法 3.5 实现单链表反转 - 第二种头插法 4.0 实现单链表反转的五种完整代码 1.0 单链表的反转说明 单链表的反转是指将链表中的节点顺序逆转即原先的链表尾部变成了头部头部变成了尾部。比如[1,2,3,4,5,6,7] 将这个链表的值反转得到的结果为[7,6,5,4,3,2,1]需要注意的是可以用值打印出来会更好观察链表反转后的结果。 2.0 单链表的创建 具体的创建思路首先要把节点进行封装成单独的类该类中的成员包括int value 存放值Node next 引用下一个节点。由于该节点类为链表中的一个组成部分因此将该类设为静态内部类外部类的成员为哨兵节点。
代码如下 import java.util.Iterator;public class Linked implements IterableInteger{private final Node hand;private int size;static class Node {public int value;public Node next;public Node(int value, Node next) {this.value value;this.next next;}}public Linked() {hand new Node(0,null);}public void addLast (int value) {Node p hand;while (p.next ! null) {p p.next;}p.next new Node(value, null);size;}public void addFirst(int value) {hand.next new Node(value,hand.next);size;}Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p hand.next;Overridepublic boolean hasNext() {return p ! null;}Overridepublic Integer next() {int k p.value;p p.next;return k;}};}} 为了方便对反转的五种方法进行讲解实现了以上的头插节点、尾插节点、用迭代器循环节点的值。 本篇重点是反转的五种的方法所以对以上的实现的 API 不太了解的话点击以下链接去了解一下 Java 数据结构篇-实现单链表核心API-CSDN博客 3.0 实现单链表反转的五种方法 迭代法遍历链表依次改变节点的指针方向使其指向前一个节点。 递归法利用递归函数先反转后续节点然后再将当前节点的指针指向前一个节点。 头插法从头到尾遍历原链表依次将每个节点插入到新链表的头部形成新的反转链表。 栈利用栈的特性将链表节点依次入栈然后依次出栈构建新的反转链表。 三指针法使用三个指针分别指向当前节点、前一个节点和后一个节点依次改变节点的指针方向实现链表的反转。 3.1 实现单链表反转 - 循环复制迭代法 思路为遍历旧的链表来取得每个节点的对应的值然后新链表根据得到的值来创建节点进行头插节点这样就实现了链表反转了。需要注意的是这个方法并没有改变旧链表。
代码如下 //方法一: 循环复制public Linked reverseMethod1 (Linked linked) {Linked linked1 new Linked();for (Integer integer : linked) {linked1.addFirst(integer);}return linked1;} 分析以上代码先创建一个新链表 linked1 然后调用头插节点的方法通过传入旧节点的值来创建对象也就是节点。需要注意的是这里的增强 for 循环是已经实现了。 3.2 实现单链表反转 - 头插法 通过改变旧节点的节点指向来实现链表反转当反转结束之后旧的链表顺序就会被改变。具体思路先要对旧节点的 hand.next 头节点从该链表独立出来对于旧链表来说就是删除头节点不过要记录要删除的节点得到这个头节点之后该节点头插到新的链表中一直循环往复下去直到 hand.next null 结束循环。 对于这个链表来说这就可以把 remove 这个节点删除了也为头删节点。当 hand.next null 就说明了没有节点了就应该结束循环了。 这就是头插节点的流程。 代码如下 //方法二: 改变旧节点的指向public Linked reverseMethod2(Linked linked) {Linked linkedNew new Linked();Node handNew linkedNew.hand;while (hand.next ! null) {//先头删Node temp linked.hand.next;linked.hand.next temp.next;//再头插Node tp handNew.next;handNew.next temp;temp.next tp;}return linkedNew;} 对以上代码进行分析 先创建一个新的链表在删除头节点前需要将要删除的节点记录起来如果一个对象没被引用就会被 JVM 自动回收然后头节点指向删除节点的指向下一个的节点。头插节点前需要将 hand.next 同样要记录然后头节点指向新的节点新的节点的下一个节点正就是原先的 hand.next 。 3.3 实现单链表反转 - 递归法 思路通过递归这种方式先递出到 “底” 得到旧链表的最后一个节点所以递归结束的条件也就是 temp.next null返回该节点 temp 也就是最后的节点。递归的函数也很容易可以想出来为 调用自己的方法名(node.next) 。
代码如下 //方法三: 递归public Linked reverseMethod3(Linked linked) {Linked linked1 new Linked();linked1.hand.next reversion(linked.hand.next);return linked1;}public Node reversion (Node node) {if (node null || node.next null) {return node;}Node last reversion(node.next);node.next.next node;node.next null;return last;} 对以上代码进行分析先创建一个新的链表 linkded1 调用 reversion() 这个方法来得到头节点。具体来看是如何得到头节点显而易见就是通过递归递到底到尽头取到最后一个节点然后将这个尾节点一直返回出来OK这里就拿到了新链表的头节点了。接下来要考虑的是如何将剩下的节点反转呢 先来看看递归的流程图 分析如下 假设有五个节点在递归回归的过程中需要做的事第五个节点指向第四个节点第四个节点指向第三个节点...一直下去这样是不是就实现了每个节点指向都反转了。但是需要注意的是当第二个节点指向第一个节点这里都没有问题我们很容易会忽略第一个节点原先就指向第二个节点因此会出现死循环解决办法先暂时将被指向的节点赋值为null 这样就完美解决了。 3.4 实现单链表反转 - 三指针法 实现思路在原先链表中进行改变每个节点的引用先定义出三个变量分别为 o1o2n1一开始的时候 o1 , n1指向链表中的 hand 头节点先来搞定没有哨兵的链表对于 o2 指向 hand.next 。接下来就可以开始移动 o2n1 这个两个指针了主要的是 o1 保持不变永远指向 hand 节点先让 hand.next o2.next 这个意思就是将 hand.next 的头节点的下一个节点从链表中移出然后将移出来的节点指向 n1 最后 o2 n1 将 n1 赋值给 o2 o2 再接着指向 hand.next 的节点。 几个简单的过程 代码如下 //方法四:双引用public Linked reverseMethod4(Linked linked) {linked.hand.next dualPointers(linked.hand.next);return linked;}public Node dualPointers(Node hand) {Node o1 hand;Node n1 hand;Node o2 o1.next;while (o2 ! null) {o1.next o2.next;o2.next n1;n1 o2;o2 o1.next;}return n1;} 通过以上的简单几个过程且结合代码来分析应该会有一点点感觉来总结以下对于 o1 的动作就是站在 hand 节点中 一动不动 对于 o2 可以将它看作搬运工不断搬运 hand.next 的节点运到 n1 节点的前面n1 的左边具体就是先要将 o2.next 节点被 hand.next 引用接着就是搬运了 o2.next 指向 n1 的节点然后 n1 需要往后跳一格往左边移动一个节点即将 o2 赋值给 n1然后 o2 就返回去指向 o1.next 的节点了循环往复下去直到当 o1.next null 时就该结束循环了。 3.5 实现单链表反转 - 第二种头插法 思路遍历旧链表的每一个节点然后直接插入到新链表中这个方法个第一种头插很相似区别就是第一种头插的方法是面向对象编程的第二种头插的方法是面向过程来编程的。
代码如下 //方法五:public Linked reverseMethod5(Linked linked) {Node o1 linked.hand.next;Linked linked1 new Linked();Node n1 null;while (o1 ! null) {Node temp o1.next;o1.next n1;n1 o1;o1 temp;}linked1.hand.next n1;return linked1;} 这里也运用到了头删还有头插跟之前的头插有所不同这里的头插是将插入进来的节点变成为新链表的头节点直到遍历结束为止。 4.0 实现单链表反转的五种完整代码 import java.util.Iterator;public class Linked implements IterableInteger{public Node hand;private int size;static class Node {public int value;public Node next;public Node(int value, Node next) {this.value value;this.next next;}}public Linked() {hand new Node(0,null);}public void addLast (int value) {Node p hand;while (p.next ! null) {p p.next;}p.next new Node(value, null);size;}public void addFirst(int value) {hand.next new Node(value,hand.next);size;}Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p hand.next;Overridepublic boolean hasNext() {return p ! null;}Overridepublic Integer next() {int k p.value;p p.next;return k;}};}//方法一: 循环复制public Linked reverseMethod1 (Linked linked) {Linked linked1 new Linked();for (Integer integer : linked) {linked1.addFirst(integer);}return linked1;}//方法二: 改变旧节点的指向public Linked reverseMethod2(Linked linked) {Linked linkedNew new Linked();Node handNew linkedNew.hand;while (hand.next ! null) {//先头删Node temp linked.hand.next;linked.hand.next temp.next;//再头插Node tp handNew.next;handNew.next temp;temp.next tp;}return linkedNew;}//方法三: 递归public Linked reverseMethod3(Linked linked) {Linked linked1 new Linked();linked1.hand.next reversion(linked.hand.next);return linked1;}public Node reversion (Node node) {if (node null || node.next null) {return node;}Node last reversion(node.next);node.next.next node;node.next null;return last;}//方法四:双引用public Linked reverseMethod4(Linked linked) {linked.hand.next dualPointers(linked.hand.next);return linked;}public Node dualPointers(Node hand) {Node o1 hand;Node n1 hand;Node o2 o1.next;while (o2 ! null) {o1.next o2.next;o2.next n1;n1 o2;o2 o1.next;}return n1;}//方法五:public Linked reverseMethod5(Linked linked) {Node o1 linked.hand.next;Linked linked1 new Linked();Node n1 null;while (o1 ! null) {Node temp o1.next;o1.next n1;n1 o1;o1 temp;}linked1.hand.next n1;return linked1;}}
