迭代反转

这是个人认为比较容易理解的，迭代是从表头开始处理，依次将每个节点变成新的表头，并将其地址域指向上一个节点（即旧的表头，若为第一个节点，则地址域指向NULL），以下面链表作为例子：
leetcode.svg

单向链表反转图示：

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

  1. public class ReverseList {
  3.     public static class ListNode {
  4.         private int value;
  5.         private ListNode next;
  7.         public ListNode(int value, ListNode next) {
  8.             this.value = value;
  9.             this.next = next;
  10.         }
  12.         public static ListNode iteration(ListNode head) {
  13.             ListNode pre = null,next;
  14.             ListNode current = head;
  15.             while (current != null) {
  16.                 // 保存当前下一个元素
  17.                 next = current.next;
  18.                 // 将当前的下一个元素, 指向前一个元素
  19.                 current.next = pre;
  20.                 // 将当前元素设置为前一个元素, 为下次循环做准备
  21.                 pre = current;
  22.                 current = next;
  23.             }
  24.             return pre;
  25.         }
  26.     }
  28.     public static void main(String[] args) {
  29.         ListNode node5 = new ListNode(5, null);
  30.         ListNode node4 = new ListNode(4, node5);
  31.         ListNode node3 = new ListNode(3, node4);
  32.         ListNode node2 = new ListNode(2, node3);
  33.         ListNode node1 = new ListNode(1, node2);
  35.         ListNode iteration = ListNode.iteration(node1);
  36.         System.out.println(iteration);
  37.     }
  38. }

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

  • next = current.next; 保留当前节点的下一个节点
  • current.next = pre; 重置当前节点的下一个节点为上一个节点
  • pre = current; 下次遍历需要用到的上一个节点
  • current= next; 下次遍历需要用到的当前节点

链表反转 - 图2
迭代法的特点是：从前向后节点之间的链接依次断开， 重置每个节点下一个节点的指向。

递归法

递归法的解题思路是：利用递归的思想和栈先进后出的特性，完成链表的反转。
要理解递归法，首先要对递归和栈的特性有一定的了解，这里简单介绍一下。

  • 递归：方法自己调用自己、递归需要有结束条件。
  • 栈:先进后出。

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

  1. public class ReverseList {
  3.     public static class ListNode {
  4.         private int value;
  5.         private ListNode next;
  7.         public ListNode(int value, ListNode next) {
  8.             this.value = value;
  9.             this.next = next;
  10.         }
  12.         /**
  13.          * 递归
  14.          *
  15.          * 栈:先进后出。
  16.          * 压栈:
  17.          *  reverseRecursion(node4)
  18.          *  reverseRecursion(node3)
  19.          *  reverseRecursion(node2)
  20.          *  reverseRecursion(node1)
  21.          * @return
  22.          */
  23.         public static ListNode reverseRecursion(ListNode head) {
  24.             if (head == null || head.next == null) {
  25.                 return head;
  26.             }
  27.             ListNode newHead = reverseRecursion(head.next);
  28.             head.next.next = head;
  29.             head.next = null;
  30.             return newHead;
  31.         }
  33.     }
  35.     public static void main(String[] args) {
  36.         ListNode node5 = new ListNode(5, null);
  37.         ListNode node4 = new ListNode(4, node5);
  38.         ListNode node3 = new ListNode(3, node4);
  39.         ListNode node2 = new ListNode(2, node3);
  40.         ListNode node1 = new ListNode(1, node2);
  42.         ListNode result = ListNode.reverseRecursion(node1);
  43.         System.out.println("end");
  44.     }
  45. }

代码解释：
ListNode newHead = reverseRecursion(head.next);
1、递归法的目的是要返回一个新的头节点，这个新的头节点是原来链表的尾节点。
2、递归是方法自己调用自己，栈的特性是先进后出、后进先出。所以这段代码的作用是不断的去压栈。
head.next.next = head; 把当前节点指向的下一个节点的指向变为自己。（不要慌，这段代码的解释，下面有图有真相）
head.next = null; 当前节点指向的下一个节点变为空。

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

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

讲真，我最开始也是想放弃的，背住代码算了。迭代法他就不香吗。。。
后来想到人类对图形的理解能力要长于文字，我们把这个过程画出来试试看能否理解。
我们还使用上文中使用过的链表作为数据源来分析这个过程
链表反转 - 图3
ListNode newHead = reverseRecursion(head.next);这段代码会执行四次，压栈四次，如图：
链表反转 - 图4
if (null == head || null == head.next) {return head;}这段代码会让 reverseRecursion(head(4)) 发生弹栈，然而链表没有发生任何变化。。。方法继续执行。
链表反转 - 图5
链表反转 - 图6

接着 reverseRecursion(head(3)) 弹栈执行下面这段代码
head.next.next = head;
head.next = null;
reverseRecursion(head(3)) 执行之后链表发生了如下变化：
image.png
下面的过程简单了 reverseRecursion(head(2))出栈。
head.next.next = head;
head.next = null;
image.png
reverseRecursion(head(1))出栈：链表反转完成，撒花🎉
head.next.next = head;
head.next = null;
image.png