143. Reorder List
C++，链表。
很显然，这道题如果用了数组/vector/栈/队列就是不及格的解法。
怎么在不用额外空间的情况下求解呢？答案是递归。
就拿题目中给的序列[1,2,3,4,5,6]举例，我们需要从中间往两边进行拆分：
- 首先递归地遍历序列，直到序列中间位置，也就是3和4
- 定义两个指针，让指针指向3和4
- 然后我们返回4后面元素的地址，也就是5的地址，退出本层函数
- 接着到了元素2，先保存3的地址，让2的next指针指向上一步中返回的5
- 让5的next指针指向刚刚保存的3
- 然后接下来同理。。。
- 最后就是1->6->2->5->3->4->nullptr
是的，递归能保存之前的过程，所以我们能从中间往两边拆分。。。
代码如下：
class Solution {
public:
void reorderList(ListNode* head) {
if (!head)
return ;
ListNode *dummy = new ListNode(0);
dummy->next = head;
head = dummy;
int cnt = 0;
while (head->next) {
head = head->next;
cnt++;
}
solve(dummy->next, cnt, 1);
head = dummy->next;
}
ListNode *solve(ListNode *root, const int &cnt, int depth) {
if (cnt % 2 == 0 && depth == cnt / 2) {
ListNode *next = root->next;
ListNode *rn_node = next->next;
next->next = nullptr;
return rn_node;
} else if (cnt % 2 == 1 && depth == cnt / 2 + 1) {
ListNode *next = root->next;
root->next = nullptr;
return next;
}
ListNode *next = solve(root->next, cnt, depth + 1);
ListNode *next_next = root->next;
root->next = next;
ListNode *rn_next = next->next;
next->next = next_next;
return rn_next;
}
};
小提示，很多同学自从用了leetcode就不会自己写测试用例了，这样是很危险的。。。
完整测试代码：
#include <cstdio>
#include <iostream>
#include <vector>
/**
* Definition for singly-linked list.
*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void reorderList(ListNode* head) {
if (!head)
return ;
ListNode *dummy = new ListNode(0);
dummy->next = head;
head = dummy;
int cnt = 0;
while (head->next) {
head = head->next;
cnt++;
}
solve(dummy->next, cnt, 1);
head = dummy->next;
}
ListNode *solve(ListNode *root, const int &cnt, int depth) {
if (cnt % 2 == 0 && depth == cnt / 2) {
ListNode *next = root->next;
ListNode *rn_node = next->next;
next->next = nullptr;
return rn_node;
} else if (cnt % 2 == 1 && depth == cnt / 2 + 1) {
ListNode *next = root->next;
root->next = nullptr;
return next;
}
ListNode *next = solve(root->next, cnt, depth + 1);
ListNode *next_next = root->next;
root->next = next;
ListNode *rn_next = next->next;
next->next = next_next;
return rn_next;
}
};
ListNode *get_list(const std::vector<int> &v) {
ListNode *dummy = new ListNode(0);
ListNode *head = dummy;
for (const int &it : v) {
head->next = new ListNode(it);
head = head->next;
}
return dummy->next;
}
void print_list(const ListNode *root) {
if (!root) return ;
std::cout << root->val << "\t";
print_list(root->next);
}
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
ListNode *root = get_list(v);
std::cout << "BEFORE:" << std::endl;
print_list(root);
std::cout << "\nAFTER:" << std::endl;
(new Solution())->reorderList(root);
print_list(root);
std::cout << std::endl;
return 0;
}
