> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/linked-list/reorder-list.md).

# Reorder List

Given a singly linked list *L*: *L*0→*L*1→…→*Ln*-1→*L*n,\
reorder it to: *L*0→*Ln*→*L*1→*Ln*-1→*L*2→*Ln*-2→…

You may **not** modify the values in the list's nodes, only nodes itself may be changed.

**Example 1:**

```
Given 1->2->3->4, reorder it to 1->4->2->3.
```

**Example 2:**

```
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
```

```java
class Solution {
    public ListNode reverse(ListNode node) {
        ListNode prev = null, temp = node;
        while (temp != null) {
            ListNode t = temp.next;
            temp.next = prev;
            prev = temp;
            temp = t;
        }
        return prev;
    }

    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode rightSide = reverse(slow.next);
        slow.next = null;
        ListNode leftSide = head;
        while (leftSide != null && rightSide!=null) {
            ListNode temp1 = leftSide.next;
            ListNode temp2 = rightSide.next;
            leftSide.next = rightSide;
            rightSide.next = temp1;
            leftSide = temp1;
            rightSide = temp2;
        }
    }
}
```