双指针

使用快慢指针先找到链表的中间节点，如果链表的节点数量是奇数个，那就是正中间那个节点；如果链表的节点数量是偶数个，那么中间节点就是偏左的那个。
中间节点找到以后，将中间节点右边的那部分链表和原链表断开，采用头插法将这部分链表逆置，然后再同时从左往右的遍历这两个部分的链表，进行节点的插入。
时间复杂度为O(n)

    public void reorderList(ListNode head) {

        if (head == null || head.next == null){
            return;
        }

        ListNode p = head;
        ListNode q = head.next;

        while (q!= null && q.next != null){
            q = q.next.next;
            p = p.next;
        }

        ListNode lastHead = new ListNode(-1);
        ListNode firstPart = p;
        p = p.next;
        firstPart.next = null;

        while (p != null){

            ListNode pre_p = p;
            p = p.next;
            pre_p.next = lastHead.next;
            lastHead.next = pre_p;
        }

        q = head;
        p = lastHead.next;

        while (p != null){

            ListNode pre_p = p;
            p = p.next;

            pre_p.next = q.next;
            q.next = pre_p;
            q = pre_p.next;
        }

    }