Reverse Linked List

题目：

Reverse a linked list.

For linked list 1->2->3, the reversed linked list is 3->2->1

分析：

无他，但手熟尔。这个程序写的次数越多越简练，现在直接拿head开刀，已经不定义curr了。

解法：

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The new head of reversed linked list.
     */
    ListNode *reverse(ListNode *head) {
        // write your code here
        if (head == NULL || head->next == NULL) {
            return head;
        }

        ListNode dummy(0);
        dummy.next = head;
        while (head->next != NULL) {
            ListNode* next = head->next;
            head->next = next->next;
            next->next = dummy.next;
            dummy.next = next;
        }
        return dummy.next;
    }
};

然而这个题目必须也要掌握recursion方法，具体如下

退出条件：

head为空或者head没有next

具体操作：

在退出的地方把newhead指向最后一个node，然后每次返回newhead就好

具体操作是在拿到newhead之后，把当前的head和next反序，head的next指向null。一点一点就反过来了。

解法：

public class Solution {
    public ListNode reverse(ListNode head) {
    // Write your solution here
        if (head == null || head.next == null) {
        return head;
        }
        ListNode newhead = reverse(head.next);
        ListNode next = head.next;
        next.next = head;
        head.next = null;
        return newhead;
    }
}