/**

143. Reorder List

https://leetcode.com/problems/reorder-list/description/

* @param {ListNode} head

* @return {void} Do not return anything, modify head in-place instead.

*/

var reorderList = function (head) {

　　if (head==null || head.next==null)

　　　　return;

　　//1.find the middle of list

　　let middle = findMiddle(head);

　　let secondHead = middle.next;

　　

　　middle.next = null;//断开中点和后一段

　　//2.reserve it

　　let reverseSecondHead = reverseLinkedList(secondHead);

　　//3.merge two list by items one by one

　　return mergeLinkedList(head,reverseSecondHead);

};

var findMiddle = function (head) {

　　let slow = head, fast = head;

　　while (fast != null && fast.next != null) {

　　　　slow = slow.next;

　　　　fast = fast.next.next;

　　}

　　return slow;

};

var reverseLinkedList = function (head) {

　　let prev = null;

　　let next = null;

　　let current = head;

　　while (current != null) {

　　　　next = current.next;

　　　　current.next = prev;//point to prve

　　　　prev = current;

　　　　current = next;

　　}

　　return prev;

};

var mergeLinkedList = function (node1,node2) {

　　//将第二个链表的元素间隔地插入第一个链表中

　　let cur = node1;

　　while (node2!=null){

　　　　let temp = node2.next;

　　　　node2.next = cur.next;

　　　　cur.next = node2;

　　　　cur = cur.next.next;

　　　　node2 = temp;

　　}

};