递归魔法-反转链表

206. 反转链表

这里是普通头插法解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

这里是递归解法

对于递归算法，最重要的是明确递归函数的定义和递归调用的逻辑。不要在我们的小脑瓜里模拟递归压栈，真的压不起（反正我是没有那个能力哈哈哈哈）

老老实实弄明白一层递归的作用，如图：

然后，写终止条件，就完事了。如图：

优雅的递归，实在是很优雅！

最后别忘了链表的末尾要指向null。

需要注意的有：

1. 递归算法要有 base case
2. 防止出现环

   class Solution {
       public ListNode reverseList(ListNode head) {
           // ListNode prev = null;
           // ListNode cur = head;
           // while(cur != null) {
           //     ListNode next = cur.next;
           //     cur.next = prev;
           //     prev = cur;
           //     cur = next;
           // }
           // return prev;
           // base case
           if (head == null || head.next == null) {
               return head;
           }
           ListNode last = reverseList(head.next);
           head.next.next = head;
           head.next = null;
           return last;
       }
   }