Reorder List · 數據結構與算法/leetcode/lintcode題解

# Reorder List ### Source - leetcode: [Reorder List | LeetCode OJ](https://leetcode.com/problems/reorder-list/) - lintcode: [(99) Reorder List](http://www.lintcode.com/en/problem/reorder-list/) ~~~ Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes' values. Example For example, Given 1->2->3->4->null, reorder it to 1->4->2->3->null. ~~~ ### 題解1 - 鏈表長度([TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")) 直觀角度來考慮，如果把鏈表視為數組來處理，那么我們要做的就是依次將下標之和為`n`的兩個節點鏈接到一塊兒，使用兩個索引即可解決問題，一個索引指向`i`, 另一個索引則指向其之后的第`n - 2*i`個節點(對于鏈表來說實際上需要獲取的是其前一個節點), 直至第一個索引大于第二個索引為止即處理完畢。既然依賴鏈表長度信息，那么要做的第一件事就是遍歷當前鏈表獲得其長度嘍。獲得長度后即對鏈表進行遍歷，小心處理鏈表節點的斷開及鏈接。用這種方法會提示 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")，也就是說還存在較大的優化空間！ ### C++ - [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。") ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: void */ void reorderList(ListNode *head) { if (NULL == head || NULL == head->next || NULL == head->next->next) { return; } ListNode *last = head; int length = 0; while (NULL != last) { last = last->next; ++length; } last = head; for (int i = 1; i < length - i; ++i) { ListNode *beforeTail = last; for (int j = i; j < length - i; ++j) { beforeTail = beforeTail->next; } ListNode *temp = last->next; last->next = beforeTail->next; last->next->next = temp; beforeTail->next = NULL; last = temp; } } }; ~~~ ### 源碼分析 1. 異常處理，對于節點數目在兩個以內的無需處理。 1. 遍歷求得鏈表長度。 1. 遍歷鏈表，第一個索引處的節點使用`last`表示，第二個索引處的節點的前一個節點使用`beforeTail`表示。 1. 處理鏈表的鏈接與斷開，迭代處理下一個`last`。 ### 復雜度分析 1. 遍歷整個鏈表獲得其長度，時間復雜度為 O(n)O(n)O(n). 1. 雙重`for`循環的時間復雜度為 (n?2)+(n?4)+...+2=O(12?n2)(n-2) + (n-4) + ... + 2 = O(\frac{1}{2} \cdot n^2)(n?2)+(n?4)+...+2=O(21?n2). 1. 總的時間復雜度可近似認為是 O(n2)O(n^2)O(n2), 空間復雜度為常數。 ****> 使用這種方法務必注意`i`和`j`的終止條件，若取`i < length + 1 - i`, 則在處理最后兩個節點時會出現環，且尾節點會被刪掉。在對節點進行遍歷時務必注意保留頭節點的信息！ ### 題解2 - 反轉鏈表后歸并既然題解1存在較大的優化空間，那我們該從哪一點出發進行優化呢？擒賊先擒王，題解1中時間復雜度最高的地方在于雙重`for`循環，在對第二個索引進行遍歷時，`j`每次都從`i`處開始遍歷，要是`j`能從鏈表尾部往前遍歷該有多好啊！這樣就能大大降低時間復雜度了，可惜本題的鏈表只是單向鏈表... 有什么特技可以在單向鏈表中進行反向遍歷嗎？還真有——反轉鏈表！一語驚醒夢中人。 ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: void */ void reorderList(ListNode *head) { if (NULL == head || NULL == head->next || NULL == head->next->next) { return; } ListNode *middle = findMiddle(head); ListNode *right = reverse(middle->next); middle->next = NULL; merge(head, right); } private: void merge(ListNode *left, ListNode *right) { ListNode *dummy = new ListNode(0); while (NULL != left && NULL != right) { dummy->next = left; left = left->next; dummy = dummy->next; dummy->next = right; right = right->next; dummy = dummy->next; } dummy->next = (NULL != left) ? left : right; //delete dummy; /* bug, delete the tail node */ } ListNode *reverse(ListNode *head) { ListNode *newHead = NULL; while (NULL != head) { ListNode *temp = head->next; head->next = newHead; newHead = head; head = temp; } return newHead; } ListNode *findMiddle(ListNode *head) { if (NULL == head || NULL == head->next) { return head; } ListNode *slow = head, *fast = head->next; while (NULL != fast && NULL != fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } }; ~~~ ### Java ~~~ /** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param head: The head of linked list. * @return: void */ public void reorderList(ListNode head) { if (head == null || head.next == null) return; // find middle ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode rHead = slow.next; slow.next = null; // reverse ListNode on the right side ListNode prev = null; while (rHead != null) { ListNode temp = rHead.next; rHead.next = prev; prev = rHead; rHead = temp; } // merge two list rHead = prev; ListNode lHead = head; while (lHead != null && rHead != null) { ListNode temp1 = lHead.next; lHead.next = rHead; rHead = rHead.next; lHead.next.next = temp1; lHead = temp1; } } } ~~~ ### 源碼分析相對于題解1，題解2更多地利用了鏈表的常用操作如反轉、找中點、合并。 1. 找中點：我在九章算法模板的基礎上增加了對`head->next`的異常檢測，增強了魯棒性。 1. 反轉：非常精煉的模板，記牢！ 1. 合并：也可使用九章提供的模板，思想是一樣的，需要注意`left`, `right`和`dummy`三者的賦值順序，不能更改任何一步。 1. 對于`new`出的內存如何釋放？代碼中注釋掉的為錯誤方法，你知道為什么嗎？ ### 復雜度分析找中點一次，時間復雜度近似為 O(n)O(n)O(n). 反轉鏈表一次，時間復雜度近似為 O(n/2)O(n/2)O(n/2). 合并左右鏈表一次，時間復雜度近似為 O(n/2)O(n/2)O(n/2). 故總的時間復雜度為 O(n)O(n)O(n). ### Reference - [Reorder List | 九章算法](http://www.jiuzhang.com/solutions/reorder-list/)