Reorder List

Question

Problem Statement

Given a singly linked list L: L_0→_L_1→…→_L__n-1→L_n,
reorder it to: _L_0→_L__n→L_1→_L__n-1→L_2→_L__n-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

" class="reference-link">题解1 - 链表长度(TLE)

直观角度来考虑，如果把链表视为数组来处理，那么我们要做的就是依次将下标之和为n的两个节点链接到一块儿，使用两个索引即可解决问题，一个索引指向i, 另一个索引则指向其之后的第n - 2*i个节点(对于链表来说实际上需要获取的是其前一个节点), 直至第一个索引大于第二个索引为止即处理完毕。

既然依赖链表长度信息，那么要做的第一件事就是遍历当前链表获得其长度喽。获得长度后即对链表进行遍历，小心处理链表节点的断开及链接。用这种方法会提示 TLE，也就是说还存在较大的优化空间！

C++ - TLE

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param head: The first node of linked list.
  17.      * @return: void
  18.      */
  19.     void reorderList(ListNode *head) {
  20.         if (NULL == head || NULL == head->next || NULL == head->next->next) {
  21.             return;
  22.         }
  24.         ListNode *last = head;
  25.         int length = 0;
  26.         while (NULL != last) {
  27.             last = last->next;
  28.             ++length;
  29.         }
  31.         last = head;
  32.         for (int i = 1; i < length - i; ++i) {
  33.             ListNode *beforeTail = last;
  34.             for (int j = i; j < length - i; ++j) {
  35.                 beforeTail = beforeTail->next;
  36.             }
  38.             ListNode *temp = last->next;
  39.             last->next = beforeTail->next;
  40.             last->next->next = temp;
  41.             beforeTail->next = NULL;
  42.             last = temp;
  43.         }
  44.     }
  45. };

源码分析

  1. 异常处理，对于节点数目在两个以内的无需处理。
  2. 遍历求得链表长度。
  3. 遍历链表，第一个索引处的节点使用last表示，第二个索引处的节点的前一个节点使用beforeTail表示。
  4. 处理链表的链接与断开，迭代处理下一个last。

复杂度分析

  1. 遍历整个链表获得其长度，时间复杂度为 $$O(n)$$.
  2. 双重for循环的时间复杂度为 $$(n-2) + (n-4) + … + 2 = O(\frac{1}{2} \cdot n^2)$$.
  3. 总的时间复杂度可近似认为是 $$O(n^2)$$, 空间复杂度为常数。

Warning 使用这种方法务必注意i和j的终止条件，若取i < length + 1 - i, 则在处理最后两个节点时会出现环，且尾节点会被删掉。在对节点进行遍历时务必注意保留头节点的信息！

题解2 - 反转链表后归并

既然题解1存在较大的优化空间，那我们该从哪一点出发进行优化呢？擒贼先擒王，题解1中时间复杂度最高的地方在于双重for循环，在对第二个索引进行遍历时，j每次都从i处开始遍历，要是j能从链表尾部往前遍历该有多好啊！这样就能大大降低时间复杂度了，可惜本题的链表只是单向链表… 有什么特技可以在单向链表中进行反向遍历吗？还真有——反转链表！一语惊醒梦中人。

C++

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param head: The first node of linked list.
  17.      * @return: void
  18.      */
  19.     void reorderList(ListNode *head) {
  20.         if (head == NULL || head->next == NULL) return;
  22.         // find middle
  23.         ListNode *slow = head, *fast = head->next;
  24.         while (fast != NULL && fast->next != NULL) {
  25.             slow = slow->next;
  26.             fast = fast->next->next;
  27.         }
  28.         ListNode *rHead = slow->next;
  29.         slow->next = NULL;
  31.         // reverse ListNode on the right side
  32.         ListNode *prev = NULL;
  33.         while (rHead != NULL) {
  34.             ListNode *temp = rHead->next;
  35.             rHead->next = prev;
  36.             prev = rHead;
  37.             rHead = temp;
  38.         }
  40.         // merge two list
  41.         rHead = prev;
  42.         ListNode *lHead = head;
  43.         while (lHead != NULL && rHead != NULL) {
  44.             ListNode *temp1 = lHead->next;
  45.             lHead->next = rHead;
  46.             ListNode *temp2 = rHead->next;
  47.             rHead->next = temp1;
  48.             lHead = temp1;
  49.             rHead = temp2;
  50.         }
  51.     }
  52. };

Java

  1. /**
  2.  * Definition for ListNode.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int val) {
  7.  *         this.val = val;
  8.  *         this.next = null;
  9.  *     }
  10.  * }
  11.  */ 
  12. public class Solution {
  13.     /**
  14.      * @param head: The head of linked list.
  15.      * @return: void
  16.      */
  17.     public void reorderList(ListNode head) {  
  18.         if (head == null || head.next == null) return;
  20.         // find middle
  21.         ListNode slow = head, fast = head.next;
  22.         while (fast != null && fast.next != null) {
  23.             slow = slow.next;
  24.             fast = fast.next.next;
  25.         }
  26.         ListNode rHead = slow.next;
  27.         slow.next = null;
  29.         // reverse ListNode on the right side
  30.         ListNode prev = null;
  31.         while (rHead != null) {
  32.             ListNode temp = rHead.next;
  33.             rHead.next = prev;
  34.             prev = rHead;
  35.             rHead = temp;
  36.         }
  38.         // merge two list
  39.         rHead = prev;
  40.         ListNode lHead = head;
  41.         while (lHead != null && rHead != null) {
  42.             ListNode temp1 = lHead.next;
  43.             lHead.next = rHead;
  44.             rHead = rHead.next;
  45.             lHead.next.next = temp1;
  46.             lHead = temp1;
  47.         }
  48.     }
  49. }

源码分析

相对于题解1，题解2更多地利用了链表的常用操作如反转、找中点、合并。

  1. 找中点：我在九章算法模板的基础上增加了对head->next的异常检测，增强了鲁棒性。
  2. 反转：非常精炼的模板，记牢！
  3. 合并：也可使用九章提供的模板，思想是一样的，需要注意left, right和dummy三者的赋值顺序，不能更改任何一步。

复杂度分析

找中点一次，时间复杂度近似为 O(n). 反转链表一次，时间复杂度近似为 O(n/2). 合并左右链表一次，时间复杂度近似为 O(n/2). 故总的时间复杂度为 O(n).

Reference