知识点：快慢指针、反转链表、合并链表、递归 时间：2020年10月20日 题目链接：https://leetcode-cn.com/problems/reorder-list/
题目 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例1 输入： 给定链表 1->2->3->4 输出： 重新排列为 1->4->2->3.
示例 2: 输入： 给定链表 1->2->3->4->5 输出： 重新排列为 1->5->2->4->3
解法
递归 太慢
我们可以看到每次取到最后的节点放到头节点的后面每一次都需要走到倒数第二个节点，进行重新排列，再次调用函数（head->next->next）线性表
链表没有下表，无法随机访问链表中任意位置的元素把所有节点放入容器中，再在容器中操作寻找链表中点 + 链表逆序 + 合并链表
找到原链表的中点 快慢指针右半边链表逆序链表合并代码
#include <stdio.h> #include <iostream> #include <vector> using namespace std; 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) { ListNode* tmp = head; int len = 0; if(tmp==nullptr||tmp->next==nullptr||tmp->next->next==nullptr)return; while(tmp->next->next!=nullptr) tmp = tmp->next; tmp->next->next = head->next; head->next = tmp->next; tmp->next = nullptr; reorderList(head->next->next); } }; class Solution { public: void reorderList(ListNode* head) { if(head == nullptr)return; vector<ListNode*> vec; ListNode *tmp = head; while(tmp!=nullptr){ vec.push_back(tmp); tmp = tmp->next; } int i=0,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; } }; class Solution { public: void reorderList(ListNode* head) { if (head == nullptr) {return;} //找到中间节点 ListNode* mid = middleNode(head); ListNode* l1 = head; ListNode* l2 = mid->next; l2 = reverseList(l2); mid->next = nullptr; mergeList(l1, l2); } ListNode* middleNode(ListNode* head) { //快慢指针 ListNode* slow = head; ListNode* fast = head; while(fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; } ListNode* reverseList(ListNode* head) { //三个节点 pre、cur、next ListNode* pre = nullptr; ListNode* cur = head; while(cur != nullptr){ ListNode* nextnode = cur->next; cur->next = pre; pre = cur; cur = nextnode; } return pre; } void mergeList(ListNode* l1, ListNode* l2) { /* l1 l1->next 1 -> 2 -> 3 l2 l2->next 5 -> 4 */ ListNode* l1_next; ListNode* l2_next; while(l1!=nullptr && l2!=nullptr){ l1_next = l1->next; l2_next = l2->next; l1->next = l2; l2->next = l1_next; l1 = l1_next; l2 = l2_next; } } }; void print_node(ListNode* head){ while(head!=nullptr){ cout<<head->val<<endl; head = head->next; } } int main() { ListNode node5(5); ListNode node4(4,&node5); ListNode node3(3,&node4); ListNode node2(2,&node3); ListNode node1(1,&node2); print_node(&node1); Solution s; s.reorderList(&node1); print_node(&node1); return 0; }今天也是爱zz的一天哦！
