# 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 };``````