Reverse Linked List

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

http://www.lintcode.com/en/problem/reverse-linked-list/

Discussion

这是一道最最基本的链表题了，简直要倒着都能写出来！递归写法非递归写法都要熟的不能再熟。

Solution

Iteration. O(n) runtime, O(1) space. 四步反转，画图防错。

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
        ListNode *pre = NULL;
        ListNode *cur = head;
        while(cur != NULL) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

Recursion. 递归的精髓就在于你可以认为处理好当前的case，递归调用同样可以处理其它的子问题了。所以关键就在于一什么时候结束，二当前的case和下一个case之间的关系是什么。

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 *newhead = reverse(head->next);//递归调用
        head->next->next = head;//处理好当前case：head会成为谁的next，head的next会变成谁。
        head->next = NULL;
        return newhead;
    }
};