描述
来源：牛客-名企高频面试题高频TOP200
将给定的单链表L：L0->L1->…->Ln-1->Ln
重新排序为：L0->Ln->L1->Ln-1->L2->Ln-2->…
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
数据范围：链表长度 0 <= n <= 20000 ，链表中每个节点的值满足 0 <= val <= 1000
要求：空间复杂度 O(n)并在链表上进行操作而不新建链表，时间复杂度 O(n)
进阶：空间复杂度 O(1) ， 时间复杂度 O(n)
答案及解析
1. 数组法
将链表存储于数组当中，通过下标重建链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void reorderList(ListNode* head)
{
if ( !head )
return;
vector<ListNode*>vec;
while ( head )
{
vec.push_back(head);
head = head->next;
}
auto i = 0;
auto j = vec.size() - 1;
while ( i < j )
{
vec[i]->next = vec[j];
++i;
if ( i == j )
break;
vec[j]->next = vec[i];
--j;
}
vec[i]->next = nullptr;
return;
}
|
时间复杂度O(N)：N是链表的结点数量，遍历链表、数组构建新链表
空间复杂度O(N)：使用额外的数组空间
2. 寻找链表中点 + 链表逆序 + 合并链表
1、找中点的话，可以使用快慢指针。快指针一次走两步，慢指针一次走一步，当快指针走到终点的话，慢指针会刚好到中点。如果节点个数是偶数的话，slow 走到的是左端点，利用这一点，我们可以把奇数和偶数的情况合并，不需要分开考虑。
2、链表逆序的话，参考反转链表
3、合并链表，两个指针分别向后移动就可以。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| ListNode* ReverseList(ListNode* pHead)
{
ListNode* nHead = nullptr;
ListNode* node = nullptr;
while ( pHead )
{
node = pHead;
pHead = pHead->next;
node->next = nHead;
nHead = node;
}
return nHead;
}
void reorderList(ListNode* head)
{
if ( !head || !head->next || !head->next->next )
return;
ListNode* slow = head;
ListNode* fast = head;
while ( fast->next && fast->next->next )
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* nHead = slow->next;
slow->next = nullptr;
nHead = ReverseList(nHead);
while ( nHead )
{
ListNode* tmp = nHead->next;
nHead->next = head->next;
head->next = nHead;
head = nHead->next;
nHead = tmp;
}
}
|
时间复杂度O(N)：N是链表的结点数量，遍历链表、重组链表
空间复杂度O(1)：使用常数级空间指针
