#### Approach #1 Extra storage [Accepted]

**Intuition**

Every $$i$$'th element is linked to $$last i$$'th element.

Basic idea is to have a quick access to element using its index and relinking elements.

// ith - k.ith

// take first half

// take second half and reverse it.

// merge both

// if a b c -> a c b

// if a b c d -> a d b c

**Algorithm**

Linked list is slow for index accesses.

Instead we can copy elements into a list. then access them by index codes.

Traversing from begining to mid point, link every $$i$$'th element to

$$size-i$$'th element. Finally make sure new tail is there (remove previous link).

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
List<ListNode> nodes = new ArrayList<>();
if(head == null)
return ;
ListNode cur = head;
while(cur!=null){
nodes.add(cur);
cur=cur.next;
}
//nodes have all. now recreate one.
int size = nodes.size();
cur=head;
for(int i=0;i<size/2;i++){
ListNode ith = nodes.get(i);
ListNode lastith = nodes.get(size-1-i);
lastith.next = ith.next;
ith.next = lastith;
}
//fix cycle
//tail should be size/2'
int mid = (size)/2;
nodes.get(mid).next = null;
}
}
```

**Complexity Analysis**

- Time complexity : So, time complexity is $$O(n+n/2) = O(n)$$.
- Space complexity : $$O(n)$$. Take a copy of all elements.