206. Reverse Linked List

题目：

Reverse a singly linked list.

思路：

以1—>2->3->4为例，链表反转的过程如下：

第一次循环结束：

head: 2->3->4->NULL

newhead: 1->NULL

第二次循环结束：

head: 3->4->NULL

newhead: 2->1->NULL

第三次循环结束：

head: 4->NULL

newhead: 3->2->1->NULL

第四次循环结束：

head: NULL

newhead: 4->3->2->1->NULL

代码：

 1 class Solution {
 2 public:
 3     ListNode* reverseList(ListNode *head) {
 4         ListNode *newHead = NULL;
 5         while (head) {
 6             ListNode *nextNode = head->next;
 7             head->next = newHead;
 8             newHead = head;
 9             head = nextNode;
10         }
11         return newHead;
12     }
13 };

 1 class Solution {
 2 public:
 3     ListNode* reverseList(ListNode *head) {
 4         return reverseListIter(head, NULL);
 5     }
 6     ListNode *reverseListIter(ListNode *head, ListNode *newhead) {
 7         if (head == NULL) {
 8             return newhead;
 9         }
10         ListNode *nextNode = head->next;
11         head->next = newhead;
12         return reverseListIter(nextNode, head);
13     }
14 };

参考：

http://www.2cto.com/kf/201601/485759.html