题目描述
题目链接: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)的先入后出,我们可以获得这个效果:
方法一
利用快慢指针,找到链表的后半段放入栈中,然后利用栈的先进后出原则将节点依次插入前半段中,这里要注意当节点个数为奇数时要保证后半段是较短的,代码如下:
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)
方法二
如果不想找中点,也可以将链表全放入栈中,然后利用链表长度来作为插入完成的指标,同样要注意末尾节点的处理,代码如下:
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)