你是风儿资料

本文主要介绍你是风儿资料 方法和在新技术下所面对的“挑战”,方便大家深入理解你是风儿资料 过程。本文也将分享你是风儿资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

单向链表反转的方法有很多,其中用的比较多的是迭代法和递归法,迭代法通俗易懂,递归法相对来说比较难理解一些。

最近读了一些网上的文章对这两种算法的解释后,有些自己的理解分享出来供大家参考。

单向链表反转图示:

你是风儿

 

一、迭代法

迭代法的解题思路是:通过循环遍历的方式,使链表的每一个节点和它的下一个节点断开,然后重置其下一个节点。

代码实现:

import lombok.AllArgsConstructor; import lombok.Data;  @Data @AllArgsConstructor public class ListNode {      private int value;      private ListNode next;       /**      * 迭代法      * @param head      * @return      */     public static ListNode reverseIterate(ListNode head){          ListNode pre = null,cur = head,next = null;          while (null != cur){             next = cur.next;             cur.next = pre;              pre = cur;              cur = next;         }          return pre;     }      public static void main(String[] args) {          ListNode listNode4 = new ListNode(4, null);         ListNode listNode3 = new ListNode(3, listNode4);         ListNode listNode2 = new ListNode(2, listNode3);         ListNode listNode1 = new ListNode(1, listNode2);          System.out.println(reverseIterate(listNode1));              } }

 代码解释:

对于链表中的一个节点(cur)来说,它包含节点的值(value)、其所指向的下一个节点(next)、及指向它的上一个节点(pre)。反转链表就是要把当前节点指向的下一个节点变成指向上一个节点。(链表头没有上一个节点,链表尾下一个节点的指向为空)

next = cur.next; 保留当前节点的下一个节点

cur.next = pre; 重置当前节点的下一个节点为上一个节点

pre = cur; 下次遍历需要用到的上一个节点

cur = next; 下次遍历需要用到的当前节点

其执行过程可以用下图表示:

你是风儿

 

 

迭代法的特点是:从前向后节点之间的链接依次断开, 重置每个节点下一个节点的指向。

二、递归法

递归法的解题思路是:利用递归的思想和栈先进后出的特性,完成链表的反转。

要理解递归法,首先要对递归和栈的特性有一定的了解,这里简单介绍一下。

递归:方法自己调用自己、递归需要有结束条件。

栈:先进后出。

要牢记这两个点,对我们理解递归法很重要。

代码实现:

import lombok.AllArgsConstructor; import lombok.Data;  @Data @AllArgsConstructor public class ListNode {      private int value;      private ListNode next;      /**      * 递归法      * @param head      * @return      */     public static ListNode reverseRecursion(ListNode head){         if (null == head || null == head.next){             return head;         }          ListNode newHead = reverseRecursion(head.next);          head.next.next = head;         head.next = null;          return newHead;     }       public static void main(String[] args) {          ListNode listNode4 = new ListNode(4, null);         ListNode listNode3 = new ListNode(3, listNode4);         ListNode listNode2 = new ListNode(2, listNode3);         ListNode listNode1 = new ListNode(1, listNode2);          System.out.println(reverseRecursion(listNode1));      } }

 

代码解释:

ListNode newHead = reverseRecursion(head.next);

1、递归法的目的是要返回一个新的头节点,这个新的头节点是原来链表的尾节点。

2、递归是方法自己调用自己,栈的特性是先进后出、后进先出。所以这段代码的作用是不断的去压栈。

head.next.next = head; 把当前节点指向的下一个节点的指向变为自己。(不要慌,这段代码的解释,下面有图有真相)

head.next = null; 当前节点指向的下一个节点变为空。

是不是看了上面的解释还有点不理解,别急,我第一次看这段代码的时候也是懵逼的(内心os:这写了个啥,怎么就反转链表了)

要理解这段代码首先,我们得去压几个栈,可能你会说我脑子里压不了几个栈容量就不够了,脑子就乱了,StackOverflowException。。。

讲真,我最开始也是想放弃的,背住代码算了。迭代法他就不香吗。。。

后来想到人类对图形的理解能力要长于文字,我们把这个过程画出来试试看能否理解。

我们还使用上文中使用过的链表作为数据源来分析这个过程

你是风儿

ListNode newHead = reverseRecursion(head.next);这段代码会执行四次,压栈四次,如图:

你是风儿  

if (null == head || null == head.next) {return head;}这段代码会让 reverseRecursion(head(4)) 发生弹栈,然而链表没有发生任何变化。。。方法继续执行。
你是风儿    你是风儿
 
接着 reverseRecursion(head(3)) 弹栈执行下面这段代码

head.next.next = head;

head.next = null;

reverseRecursion(head(3)) 执行之后链表发生了如下变化:

 

你是风儿     你是风儿

 

下面的过程简单了 reverseRecursion(head(2))出栈。

head.next.next = head;

head.next = null;

你是风儿    你是风儿

reverseRecursion(head(1))出栈:链表反转完成,撒花🎉

head.next.next = head;

head.next = null;

你是风儿你是风儿

 

以上就是我对单向链表反转迭代法和递归这两种方法的理解,希望可以帮到你。

 

 

 

 

 

 

你是风儿资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 你是风儿资料

提供最优质的资源集合

立即查看 了解详情