# 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:**

![](https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg)

```
**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

```java
/**
 * 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;
    }
}
```