# [leetcode] Reorder List

### Reorder List

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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}`.

The algorithm is straightforward.

First, divide the linked list into two parts equally. (left part may be longer than right part by one node)

Second, reverse the right part list.

Third, link the two parts craftily.

```//What if the list is empty?
//What if the list contains odd elements?
//What time complexity?
//space complexity o(1)

//1. split the list into two parts
//2. reverse the right part list
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//extreme cases

//ordinary cases
//1. find the mid of the list
ListNode * fast, * slow;
while(fast->next != NULL && fast->next->next != NULL){
fast = fast->next->next;
slow = slow->next;
}
ListNode * rightStart = slow->next; // rightStart may be NULL
slow->next = NULL;
rightStart = reverse(rightStart);
//list left may be longer than right by one node
while(rightStart != NULL){
ListNode * leftNext = leftStart->next;
ListNode * rightNext = rightStart->next;
leftStart->next = rightStart;
rightStart->next = leftNext;
leftStart = leftNext;
rightStart = rightNext;
}

}
ListNode * prev, * cur, * next;
prev = NULL;