0%

[Leetcode]143. Reorder List (C++)

题目描述

题目链接:143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

例子

例子 1

Given 1->2->3->4, reorder it to 1->4->2->3.

例子 2

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解题思路

这道题目的思路主要在于怎么从后往前获得节点,通过栈(stack)的先入后出,我们可以获得这个效果:

方法一

利用快慢指针,找到链表的后半段放入栈中,然后利用栈的先进后出原则将节点依次插入前半段中,这里要注意当节点个数为奇数时要保证后半段是较短的,代码如下:

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
37
38
39
class Solution {
public:
void reorderList(ListNode* head) {
if (!head || !head->next || !head->next->next) return;

// find median
ListNode* fast = head, *slow = head;
ListNode* tail;
while (fast && fast->next) {
fast = fast->next->next;
tail = slow;
slow = slow->next;
}
if (fast) {
tail = slow;
slow = slow->next;
}
// cut list into two half
tail->next = nullptr;

// push second half list to a stack
std::stack<ListNode*> second_half;
while(slow) {
second_half.push(slow);
slow = slow->next;
}

// concatanate two half
ListNode* curr = head;
while (!second_half.empty()){
ListNode* nextNode = second_half.top();
second_half.pop();
nextNode->next = curr->next;
curr->next = nextNode;
curr = curr->next->next;
}

}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法二

如果不想找中点,也可以将链表全放入栈中,然后利用链表长度来作为插入完成的指标,同样要注意末尾节点的处理,代码如下:

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
class Solution {
public:
void reorderList(ListNode* head) {
int length = 0;
ListNode* curr = head;
std::stack<ListNode*> node_stack;
while (curr) {
length++;
node_stack.push(curr);
curr = curr->next;
}

if (length <= 2) return;

curr = head;
int count = 0;
ListNode* nextNode;
while (count < length - 1) {
nextNode = node_stack.top();
node_stack.pop();

nextNode->next = curr->next;
curr->next = nextNode;
curr = curr->next->next;

count+= 2;
}

if (count == length - 1) {
curr->next = nullptr;
} else {
nextNode->next = nullptr;
}
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)