Reverse Linked List

题目：

单链表逆置，必须掌握

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解析：

迭代

排除没有节点和单个节点的情况后，用a,b,c标记三个相邻链表，让b指向a然后在将三个节点顺次移动。注意要判断c是否存在，因为c若已经为null的话c->next会引发时间超出的错误

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* reverseList(ListNode* head) {
12         if(head == NULL || head->next == NULL)
13             return head;
14         ListNode* a = head;
15         ListNode* b = a->next;
16         ListNode* c = b->next;
17         a->next = NULL;
18         while(b != NULL)
19         {
20             b->next = a;
21             a = b;
22             b = c;
23             if(c != NULL)
24                 c = c->next;
25         }
26         return a;
27     }
28 };

递归

递归比较难想啊：

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