206.Reverse Linked List
206.Reverse Linked List
难度:Easy
反转一个单链表。
1
示例:
2
3
输入: 1->2->3->4->5->NULL
4
输出: 5->4->3->2->1->NULL
Copied!
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
递归: 由于递归都是一层一层处理的,如果要递归,首先要处理最后一个节点,然后将剩余的继续反转,代码如下:
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) return NULL;
13
if(!head->next) {head->next=NULL; return head;}
14
ListNode* pt=head;
15
while(pt->next->next)
16
{
17
pt=pt->next;
18
}
19
ListNode* t=pt->next;
20
pt->next=NULL;
21
t->next=reverseList(head);
22
return t;
23
24
25
}
26
};
Copied!
迭代: 在遍历列表时,将当前节点的下一个节点之前前一个元素,实现反转:
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) return NULL;
13
ListNode* prev=NULL;
14
ListNode* curr=head;
15
while(curr!=NULL)
16
{
17
ListNode* tmp=curr->next;
18
curr->next=prev;
19
prev=curr;
20
curr=tmp;
21
}
22
23
24
25
return prev;
26
}
27
28
};
Copied!
Copy link