Powered By GitBook
143.Reorder List

143.Reorder List

难度:Medium
给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
1
示例 1:
2
3
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
4
示例 2:
5
6
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
Copied!
Method: Stack's FILO
1
/**
2
* Definition for singly-linked list.
3
* struct ListNode {
4
* int val;
5
* ListNode *next;
6
* ListNode() : val(0), next(nullptr) {}
7
* ListNode(int x) : val(x), next(nullptr) {}
8
* ListNode(int x, ListNode *next) : val(x), next(next) {}
9
* };
10
*/
11
class Solution {
12
public:
13
void reorderList(ListNode* head) {
14
if(!head || !head->next || !head->next->next) return;
15
ListNode* mid= head;
16
ListNode* last=head;
17
while( last->next && last->next->next)
18
{
19
mid=mid->next;
20
last=last->next->next;
21
}
22
stack<ListNode*> lastMid;
23
last=mid->next;
24
mid->next=nullptr;
25
while(last)
26
{
27
ListNode* tmp=last;
28
last=last->next;
29
tmp->next=nullptr;
30
lastMid.push(tmp);
31
32
}
33
ListNode* cur=head;
34
while(!lastMid.empty())
35
{
36
ListNode* tmp= lastMid.top();
37
tmp->next= cur->next;
38
cur->next=tmp;
39
lastMid.pop();
40
cur=tmp->next;
41
}
42
}
43
};
Copied!
执行用时 :68 ms, 在所有 C++ 提交中击败了31.46%的用户 内存消耗 :18.1 MB, 在所有 C++ 提交中击败了9.17%的用户
Last modified 1yr ago
Copy link