206：翻转链表

问题描述

反转一个单链表。

示例

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

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

思路

经典的数据结构问题。
由于头插法建立单链表是跟输入顺序逆序的，我们可以假定给定的链表是数据来源，重新按照头插法建立一个新链表即可。具体怎么做？用一个cur来指示剩余链表的头结点，每次都让它断链(在断链前要暂存它)，然后用头插法接在新的链表上，更新head的指向。(方法一 迭代)
进阶中说了可以用递归的方法来做(我浪费了20分钟在这里)。递归的思想就是我们假定递归函数能返回给我们规模缩小的同样类型问题的结果，我们只需要利用这个结果即可。

1->2->3->4->5->null

我们假定递归函数可以返回给我们2-5正确的逆序链表。

↑->->->->->↓
1 5->4->3->2->null

所以我们此时要做的是，把1插入到2的后面。怎么插入呢？我们现在只有指向5的指针trueHead和指向1的指针head. 所以我们先要把2的指向改为1，然后把1的指向改为null。 （为什么不先改变1的指向？如果我们先改变1的指向的话，我们就会遗失快速找到2的指针。）
我们还需要控制一下递归退出条件：
如果head是个null或者head.next是个null,则直接返回head.

（以上为方法二）

图解

方法一

Java版

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode cur = head.next;
        ListNode tmp;
        head.next = null;
        while(cur!=null){
            tmp = cur;
            cur = cur.next;
            tmp.next = head;
            head = tmp;
        }
        return head;
    }
}

方法二

Java版

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next==null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}