Reverse Linked List

[walterzhu29]

Description:

Reverse a linked list.

Example:

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

Link:

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

解题思路：

针对每个节点curr，只要改变该节点的next，让其指向curr前一个节点（需要用一个变量prev储存），然后再对这个节点的下个节点进行相同的操作。
这道题搞清楚以后，针对k-group那道题的反转代码就会写了。

Tips:

在进行反转操作之后，head已经不是第一个节点了而是最后一个，此时用dummy并不好用，反而直接返回prev这个点方便。

Time Complexity：

O(n)，n为节点个数

完整代码：

ListNode *reverse(ListNode *head) 
    {
        ListNode *temp; 
        ListNode *curr = head; 
        ListNode *prev = NULL;
        while(curr != NULL)
        {
            temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }