Solution by rondik

  • 0

    Approach #1 Extra storage [Accepted]

    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

    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;
            //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;
            //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.

Log in to reply

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