# 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/)
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume