/** * Source : https://oj.leetcode.com/problems/reorder-list/ * * Given a singly linked list L: L0→L1→…→Ln-1→Ln, * reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… * * You must do this in-place without altering the nodes' values. * * For example, * Given {1,2,3,4}, reorder it to {1,4,2,3}. */public class RecordList {    /**     * 将链表的后半部分翻转之后依次插入链表前半部分每个元素后面     *     * 设链表长度为n     * 1. 找到链表后半部分起始位置： n/2+1，使用双指针法，slow每次移动一个，fast每次移动两个，fast移动到最后的时候，slow指向的正好是 n/2+1     * 2. 反转后半部分连链表     * 3. 将反转后的后半部分链表依次插入前半部分,left指向左边，right指向反转后的第一个node，依次插入left的后一个，直到right指向null，     *      right每次移动一个node，left每次移动2个node（因为刚刚left后面插入一个节点）     *     * @param head     * @return     */    public LinkedNode record (LinkedNode head) {        if (head == null || head.next == null) {            return head;        }        LinkedNode midNode = findMidNode(head);        LinkedNode reversedList = reverse(midNode);        LinkedNode left = head;        LinkedNode right = reversedList;        while (right != null && right.next != null) {            // 记录将要被插入的元素            LinkedNode target = right;            // 下一个需要被插入的元素            right = right.next;            // 插入target到链表中            target.next = left.next;            left.next = target;            left = left.next.next;        }        return head;    }    private LinkedNode findMidNode (LinkedNode head) {        LinkedNode slow = head;        LinkedNode fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;        }        return slow;    }    private LinkedNode reverse (LinkedNode head) {        LinkedNode p = head;        LinkedNode pre = null;        while (p != null) {            LinkedNode next = p.next;            p.next = pre;            pre = p;            p = next;        }        return pre;    }    private class LinkedNode {        int value;        LinkedNode next;    }    /**     * 创建普通的链表     * @param arr     * @return     */    public LinkedNode createList (int[] arr) {        if (arr.length == 0) {            return null;        }        LinkedNode head = new LinkedNode();        head.value = arr[0];        LinkedNode pointer = head;        for (int i = 1; i < arr.length; i++) {            LinkedNode node = new LinkedNode();            node.value = arr[i];            pointer.next = node;            pointer = pointer.next;        }        return head;    }    private static void print (LinkedNode head) {        if (head == null) {            System.out.println("[]");        }        StringBuffer stringBuffer = new StringBuffer("[");        while (head != null) {            stringBuffer.append(head.value);            stringBuffer.append(",");            head = head.next;        }        stringBuffer.deleteCharAt(stringBuffer.length()-1);        stringBuffer.append("]");        System.out.println(stringBuffer);    }    public static void main(String[] args) {        RecordList recordList = new RecordList();        int[] arr = new int[]{1,2,3,4,5,6};        print(recordList.record(recordList.createList(arr)));    }}