LeetCode (3) 反转链表

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

方法

1. 迭代
2. 递归

解题思路

迭代思路

双链表法：我重新创建一个链表，来保存这个反转后的链表，那么我每次循环原始的链表，把原始链表的值放入到新链表，那么串起来新链表的第一个值就是旧链表的最后一个值！

递归

思路1：

把上面的迭代方式转成递归方式，一个参数为prev，表示遍历的链表的前一个节点也代表新的链表，对于递归我们要学会整体对待，也就是我不考虑怎么实现的，但是我现在定义了一个方法，假定通过这个方法我们可以实现这个问题。

所以大概的递归函数就是

reverseRecursion{

递归结束条件；

保存下current的next；

将current的next指向prev；

return reverseRecursion(current,保存下来的current的next);

}

递归还有个最重要的就是什么时候结束递归，这里我们可以试着用一个节点的场景试想，当一个节点进来，current是这个节点，prev也就是我们的实际返回的链表还是null，所以要执行一次反转处理，完成赋值，然后第二次执行函数的时候要结束递归，返回prev。

这种思路的递归是从前往后执行的思想。

思路2：

如图，假设还是反转1,2,3,4这个链表，但是这时候我们采取另一个角度来看我们把2,3,4看做一个已经通过递归函数反转之后的一个新链表，虽然我们暂时还不知道递归函数长什么样，那么这时候我们要做的事情似乎就变得非常简单了！只要把1的next也就是整体已经反转的结果的next指向1，1的next指向null，再把整体的链表返回就完成了！

同样递归问题，它的结束条件是非常重要的，当head是null或者只有一个节点时（head.next==null）直接return即可1。

这种思路的递归其实是从后往前的思想，也就是将后半部分看做已经是反转好的链表了。

完整代码

迭代思路

package org.chenly.study;

/**
 * 反转链表
 *
 * @author chenly
 * @create 2020-11-06 22:39
 */
public class ReverseLinkedList {

   public static class ListNode {
      int val;

      ListNode next;

      public ListNode(int val) {
         this.val = val;
      }

      public ListNode(int val, ListNode next) {
         this.val = val;
         this.next = next;
      }
   }

   public static void main(String[] args) {
      ListNode node1 = new ListNode(1, new ListNode(3, new ListNode(6, new ListNode(0))));

      //System.out.println(reverser(node1));

      System.out.println(reverser2(node1));

      System.out.println(reverser3(node1));

      System.out.println("");
   }

   /**
    * 迭代双链表
    */
   private static ListNode reverser(ListNode head) {
      ListNode prev = null;
      ListNode current = head;

      while (current != null) {
         ListNode temp = current.next;
         current.next = prev;

         prev = current;
         current = temp;
      }
      return prev;
   }

   /**
    * 递归实现双链表
    */
   private static ListNode reverser2(ListNode head) {

      return reverseRecursion(null, head);
   }

   private static ListNode reverseRecursion(ListNode prev, ListNode current) {
      if (current == null) {
         return prev;
      }
      ListNode temp = current.next;
      current.next = prev;
      return reverseRecursion(current, temp);

   }

   private static ListNode reverser3(ListNode head) {

      if (head == null || head.next == null) {
         return head;
      }
      ListNode afterReverse = reverser3(head.next);

      head.next.next = head;
      head.next = null;
      return afterReverse;

   }
}