# 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}.

### C++ - TLE

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @return: void
*/
return;
}

int length = 0;
while (NULL != last) {
last = last->next;
++length;
}

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. 异常处理，对于节点数目在两个以内的无需处理。
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 使用这种方法务必注意ij的终止条件，若取i < length + 1 - i, 则在处理最后两个节点时会出现环，且尾节点会被删掉。在对节点进行遍历时务必注意保留头节点的信息！

## 题解2 - 反转链表后归并

### C++

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @return: void
*/

// find middle
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
slow->next = NULL;

// reverse ListNode on the right side
ListNode *prev = NULL;
}

// merge two list
}
}
};


### Java

/**
* Definition for ListNode.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int val) {
*         this.val = val;
*         this.next = null;
*     }
* }
*/
public class Solution {
/**
* @return: void
*/

// find middle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = null;

// reverse ListNode on the right side
ListNode prev = null;
}

// merge two list
}
}
}


### 源码分析

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