例题 nc78 反转链表 nc50 链表中的节点每K个一组翻转
栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| ListNode* reverseList(ListNode* head) {
Stack<ListNode*> s;
while (head) {
s.push(head);
head = head->next;
}
if (s.empty())
return null;
ListNode* node = s.top(); s.pop();
ListNode* nhead = node;
while (!s.empty()) {
ListNode* tmp = s.top(); s.pop();
node->next = tmp;
node = node->next;
}
node->next = null;
return nhead;
}
|
头插法
1
2
3
4
5
6
7
8
9
10
| ListNode* reverseList(ListNode* head) {
ListNode* nhead = nullptr;
while(head) {
ListNode* nxt = head->next;
head->next = nhead;
nhead = head;
head = nxt;
}
return nhead;
}
|
递归法
1
2
3
4
5
6
7
8
| ListNode* reverseList(ListNode* head) {
if (!head || !head.next)
return head;
ListNode* reverse = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return reverse;
}
|
尾递归(相当于把头插法改成了递归形式，比👆的递归好一些)
1
2
3
4
5
6
7
8
9
10
| ListNode* reverseList(ListNode* head) {
return helper(head, nullptr);
}
ListNode* helper(ListNode* head, ListNode* nhead) {
if(!head) return nhead;
ListNode* nxt = head->next;
head->next = nhead;
return helper(nxt, head);
}
|