Problem:

Reverse a singly linked list.

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

Summary:

翻转链表。

Analysis:

1. Iterative solution

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         ListNode *pre = NULL;13         14         while (head != NULL) {15             ListNode *tmp = head->next;16             head->next = pre;17             pre = head;18             head = tmp;19         }20         21         return pre;22     }23 };

 2. Recursive solution

若链表为n₁->n₂->...->n_k-1->n_k->n_k+1->...->n_m->NULL

假设n_k+1到n_m的部分已翻转：n₁->n₂->...->n_k-1->n_k->n_k+1<-...<-n_m

我们若要使n_k+1的next指针指向n_k，则我们需要做的是：n_k->next->next = n_k

需要注意的是需要将n₁的next指针指向NULL。

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         }15         16         ListNode *tmp = reverseList(head->next);17         head->next->next = head;18         head->next = NULL;19         20         return tmp;21     }22 };

 

Reference: