# 143 - Reorder List

## 解法一 - Fast & Slow Pointer

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return;

// Find the middle of list

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

// reverse the second half of the list
ListNode* second = reverse(slow);

// construct the new list by interleaving two halves
while(first != NULL && second != NULL) {
ListNode* tmp = first->next;
first->next = second;
first = tmp;

tmp = second->next;
second->next = first;
second = tmp;
}

if(first != NULL)
first->next = NULL;
}

private:
ListNode* prev = NULL;

}

return prev;
}
};
``````

Runtime: 44 ms, faster than 95.04% of C++ online submissions for Reorder List. Memory Usage: 12.1 MB, less than 88.24% of C++ online submissions for Reorder List.

## 解法二 - vector 儲存 + Two Pointer

``````class Solution {
public:

vector<ListNode*> vl;
}

// reassign the next pointer
int i = 0, j =  vl.size() - 1;
while ( i + 1 < j ) {
vl[i]->next = vl[j];
vl[j]->next = vl[i+1];
++i, --j;
}

vl[j]->next = NULL;
}
};
``````