题目:
Reverse a linked list.
Example
For linked list 1->2->3
, the reversed linked list is 3->2->1
题解:
Solution 1 ()
class Solution {
public:
ListNode *reverse(ListNode *head) {
if (!head) {
return head;
}
ListNode *prev = nullptr;
while (head) {
ListNode *tmp = head->next;
head->next = prev;
prev = head;
head = tmp;
} return prev;
}
};
The basic idea of this recursive solution is to reverse all the following nodes after head
. Then we need to set head
to be the final node in the reversed list. We simply set its next node in the original list (head -> next
) to point to it and sets its next
to be NULL
.
Solution 2 ()
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !(head -> next)) return head;
ListNode* node = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
return node;
}
};
疑问?为啥下面这段程序是错的
class Solution {
public:
ListNode *reverse(ListNode *head) {
if (!head) {
return head;
}
ListNode *prev = nullptr;
while (head) {
ListNode *tmp = head;
head->next = prev;
prev = head;
head = tmp->next; } return prev;
}
};
若一定要tmp保存head,那么程序应该如下
class Solution {
public:
ListNode *reverse(ListNode *head) {
if (!head) {
return head;
}
ListNode *prev = nullptr;
while (head) {
ListNode *tmp = new ListNode(-);
*tmp = *head;
head->next = prev;
prev = head;
head = tmp->next;
delete tmp;
} return prev;
}
};
解惑:
int main()
{
ListNode* tmp = new ListNode();
ListNode* p = new ListNode();
ListNode* q = new ListNode();
ListNode* r = new ListNode();
ListNode** t = &tmp;
tmp->next = p;
p->next = q;
q->next = r; t = &((*t)->next);
(*t) = (*t)->next; cout << (*t)->val << endl;
cout << tmp->next->val << endl;
cout << (*p).val << endl; return ;
}
输出为:2 2 1