题目
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.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3. Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list
解法１：使用vector，将列表转换为数组
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
// boundary case: null
if (!head) return;
vector<ListNode*> l;
ListNode* now = head;
while (now) {
l.push_back(now);
now = now->next;
}
// boundary case: one node
if (l.size() == 1) return;
int i = 0;
int j = l.size() - 1;
now = l[i];
now->next = l[j];
now = now->next;
++i;
--j;
while (i < j) {
now->next = l[i];
now = now->next;
now->next = l[j];
now = now->next;
++i;
--j;
}
if (i == j) {
now->next = l[i];
now = now->next;
}
now->next = nullptr;
}
};
解法2: 将列表拆分＋反转＋合并
我个人认为，这一方法虽然节省空间，但是时间消耗较大。而且工程实践较复杂，略过。
