# reorder list

## reorder list

### easy problem

A lot of problems in leetcode help us to pratice some basic skills.This problem is not hard, just cut it into three parts and solve one by one.

- Find the midpoint of the list.
- Reverse the second half of the list.
- Connect the elements one by one.

### Mistakes

- Finding the midpoint, mind where the fast and slowpointer start.
- Reverse the list, do not forget the first element.

### code

```
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 void reorderList(ListNode *head) {
12 if ( !head || !head->next || !head->next->next ) {
13 return;
14 }
15 ListNode* slow = head;
16 ListNode* fast = head;
17 while( fast->next && fast->next->next ) {
18 fast = fast->next->next;
19 slow = slow->next;
20 }
21 fast = slow->next;
22 slow->next = NULL;
23 slow = head;
24 ListNode* p = fast->next;
25 ListNode* q = NULL;
26 fast->next = NULL;
27 while ( p ) {
28 q = p->next;
29 p ->next = fast;
30 fast = p;
31 p = q;
32 }
33 head = slow;
34 slow = slow->next;
35 head->next = NULL;
36 p = head;
37 int i = 0;
38 while ( slow && fast ) {
39 if ( i%2 ) {
40 p->next = slow;
41 slow = slow->next;
42 } else {
43 p->next = fast;
44 fast = fast->next;
45 }
46 i++;
47 p = p->next;
48 }
49 if ( slow ) {
50 p->next = slow;
51 }
52 if ( fast ) {
53 p->next = fast;
54 }
55 }
56 };
```