Solution by rondik


  • 0
    R

    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.

Log in to reply
 

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