# 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}.

Method:

Reverse the second part of the linkedlist, and then combine them.

Solution:

Time: O(n)
Space: O(1)

```/**
* Definition for singly-linked list.
* class ListNode {
*     public int val;
*     public ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
//    s  f
//       s    f
// 1->2->3->4 => 3
//    s  f
//       s     f
// 1->2->3->4->5 => 3
private ListNode findMid(ListNode A) {
ListNode slow = A;
ListNode fast = A;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

// 1->2->3->4
// 1<-2->3->4
private ListNode reverse(ListNode A) {
ListNode prev = null;
ListNode curr = A;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}

// 1->2->3
// 5->4->3

// 1->2->3
// 4->3
public ListNode reorderList(ListNode A) {
if (A == null || A.next == null) {
return A;
}
ListNode mid = findMid(A);
mid = reverse(mid);
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while (A.next != null && mid != null) {
ListNode Anext = A.next;
p.next = A;
p = p.next;
p.next = mid;
p = p.next;
A = Anext;
mid = mid.next;
}

return dummy.next;
}
}```

```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ListNode mid = findMid(head);
ListNode a = head;
ListNode b = reverse(mid);

merge(a, b);
}

private void merge(ListNode a, ListNode b) {
// 1 -> 2 -> 3
// 5 -> 4
ListNode pA = a;
ListNode pB = b;
while (pA != null && pB != null) {
ListNode aNext = pA.next;
ListNode bNext = pB.next;
pA.next = pB;
pB.next = aNext;
pA = aNext;
pB = bNext;
}
}

private ListNode reverse(ListNode head) {
//         1 -> 2 -> 3 -> 4
// null <- 1 <- 2 -> 3 -> 4
ListNode p = head;
ListNode prev = null;
while (p != null) {
ListNode next = p.next;
p.next = prev;
prev = p;
p = next;
}
return prev;
}

private ListNode findMid(ListNode head) {
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
if (fast == null) {
ListNode ret = slow;
prev.next = null;
return ret;
}
if (fast.next == null) {
ListNode ret = slow.next;
slow.next = null;
return ret;
}
}