206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?
反转链表。有两种方法可以解决:

1.迭代

 1 struct ListNode* reverseList(struct ListNode* head) {
 2     if(!head)   return NULL;
 3     struct ListNode *prev=NULL,*next;
 4     while(head){
 5         next=head->next;
 6         head->next=prev;
 7         prev=head;
 8         head=next;
 9     }
10     return prev;
11 }

2.递归

 1 //递归方式
 2 Node * reverseList(List head)
 3 {
 4     //如果链表为空或者链表中只有一个元素
 5     if(head == NULL || head->next == NULL)
 6     {
 7         return head;
 8     }
 9     else
10     {
11         //先反转后面的链表，走到链表的末端结点
12         Node *newhead = reverseList(head->next);
13         //再将当前节点设置为后面节点的后续节点
14         head->next->next = head;
15         //原本的head指向关系给设置成NULL，不然head会指向后面结点报错 
16         head->next = NULL;
17         
18         return newhead;
19     }
20 }