*143. Reorder List[Easy]

143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

Example

Input: head = [1,2,3,4]
Output: [1,4,2,3]

思路

• 通过快慢指针找中点
• 通过反转链表反转后半段
• 后半段依次插入前半段

题解

    public void reorderList(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        // 通过快慢指针找到中点
        /**
         * 1->2->3->4->5
         * 1->2->3
         * 4->5
         */
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // first就是前半段链表，second就是后半段链表，做分割
        ListNode first, second, pre;
        first = head;

        // 临时变量
        pre = slow.next;
        // 初始化second且给前半段链表设终止符
        second = slow.next = null;

        // 反转链表
        /**
         * 1->2->3->4->5
         * 1->2->3
         * 5->4
         */
        while (pre != null) {
            ListNode temp = pre.next;
            pre.next = second;
            second = pre;
            pre = temp;
        }

        /**
         * 后半段依次插入前半段
         */
        ListNode temp1, temp2;
        while (second != null) {
            temp1 = first.next;
            temp2 = second.next;

            first.next = second;
            second.next = temp1;

            first = temp1;
            second = temp2;
        }
    }