首页 > 代码库 > 206. Reverse Linked List

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

206. Reverse Linked List