題目: LeetCode - 143. Reorder List
題目說明
給一個 List,依照題目的要求重新排序。
※ 題目規定不能改變 node
的值。
解題思路
我們先取得中間的節點 ( 方法可以參考本篇文章:LeetCode - 876 解題紀錄 ),接著將中間到尾端的節點反轉,最後依照要求重新連接即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| class Solution { public: void reorderList(ListNode* head) { if(!head) return; auto mid = findMid(head), l1 = head, l2 = mid->next; mid->next = nullptr; l2 = _reverse(l2); while(l1 && l2) { auto _next = l1->next; l1->next = l2; l2 = l2->next; l1->next->next = _next; l1 = _next; } } private: ListNode* findMid(ListNode* head) { auto slow = head, fast = head; while(fast && fast->next) fast = fast->next->next, slow = slow->next; return slow; } ListNode* _reverse(ListNode* head) { ListNode* newhead = nullptr; while(head) { auto _next = head->next; head->next = newhead; newhead = head; head = _next; } return newhead; } };
|