0143. Reorder List

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

Description

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.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].

• 1 <= Node.val <= 1000

ac

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        // corner cases
        if (head == null || head.next == null || head.next.next == null) return;

        // find mid, O(n)
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // reverese second half, O(n/2)
        ListNode l2 = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (l2 != null ){
            ListNode tmp = l2;
            l2 = l2.next;
            tmp.next = prev;
            prev = tmp;
        }
        l2 = prev;

        // merge O(n)
        ListNode l1 = head.next;
        ListNode ranger = head;
        while (l1 != null) {
            ranger.next = l2;
            l2 = l2.next;
            ranger = ranger.next;

            ranger.next = l1;
            l1 = l1.next;
            ranger = ranger.next;
        }
        ranger.next = l2;
    }
}