# Solution by rondik

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

Intuition
Every \$\$i\$\$'th element is linked to \$\$last i\$\$'th element.
// 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).

``````
/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
List<ListNode> nodes = new ArrayList<>();

return ;

while(cur!=null){
cur=cur.next;
}

//nodes have all. now recreate one.
int size = nodes.size();

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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.