Loading... 一个包含 `n` 个元素的线性链表： ``` L = (a1, a2, …, an-2, an-1, an) ``` 现在要对其中的结点进行重新排序，得到一个新链表： ``` L' = (a1, an, a2, an-1, a3, an-2, …) ``` ### 样例1 ``` 输入：1->2->3->4 输出：1->4->2->3 ``` ### 样例2 ``` 输入：1->2->3->4->5 输出：1->5->2->4->3 ``` ### 数据范围 * 1 ≤ n ≤ 1000 * 1 ≤ ai ≤ 10000 ### 题目分析 因为笔试要求空间O(1),故使用迭代的方式来解决。 如不考虑空间复杂度的话，可以考虑使用回溯算法，即先递归到链表末元素，回溯时再进行merge操作。 ### 代码实现 迭代 ``` /* * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void rev(ListNode*& prev, ListNode*& fir) { while(fir->next) { auto ne = fir->next; fir->next = prev; prev = fir; fir = ne; } fir->next = prev; } void rearrangedList(ListNode* head) { int cnt = 0; for (auto i = head; i; i = i->next) ++cnt; if (cnt == 1) return ; cnt = (cnt >> 1); auto sec = head; while(cnt--) sec = sec->next; auto ft = sec; sec = sec->next; ft->next = 0; // reverse from sec to end; auto prev = (ListNode*)0; rev(prev,sec); // merge while(sec) { auto fne = head->next; head->next = sec; auto sne = sec->next; sec->next = fne; sec = sne; head = fne; } } }; ``` 最后修改：2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏