# 0143. Reorder List
###### tags: `Leetcode` `Medium` `Linked List`
Link: https://leetcode.com/problems/reorder-list/
## 思路 $O(N)$ $O(1)$
首先找到linkedlist的mid，然后reverse后半段，把前半段和后半段堪称两个分离的list，最后merge起来
**注意：找mid的时候，如果是找靠左边的中点，while的判断条件就是```fastRunner.next!=null && fastRunner.next.next!=null```，如果找靠右边的中点，判断条件就是```fastRunner!=null && fastRunner.next!=null```**
## Code

class Solution {
    public void reorderList(ListNode head) {
        if(head==null) return;
        ListNode mid = findMid(head);
        ListNode p2 = reverse(mid.next);
        mid.next = null;
        ListNode p1 = head;
        while(p1!=null&&p2!=null){
            ListNode next = p1.next;
            p1.next = p2;
            p2 = p2.next;
            p1.next.next = next;
            p1 = next;
        }
    }
    
    private ListNode findMid(ListNode head){
        ListNode fastRunner = head;
        ListNode slowRunner = head;
        while(fastRunner.next!=null && fastRunner.next.next!=null){
            fastRunner = fastRunner.next.next;
            slowRunner = slowRunner.next;
        }
        return slowRunner;
    }
    
    private ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}