Solution by rondik


  • 0
    R

    Approach #1 Two Pointers [Time Limit Exceeded]

    Intuition
    Find the $$k$$'th position from the end, cut the list form there then move second part in front of first part.

    Algorithm
    List is Single Linked List and we need to cut it at k'th position from tail. As there is only forward links, we need to figure out a way to find it form beginin of linked list.
    One quick approach will be iteration form the head to tail and cmoputing the list $$length$$. then the cut point will be $$length-k$$'th position. Then in a second tour the list will be cut at that point and and the second half will be moved to in front of the List.

    
    /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
    class Solution {
       public ListNode rotateRight(ListNode head, int k) {        
           if(head == null || k ==0 )
                return head;
           
           ListNode first;
           ListNode second;
           first=head;
           int i=0;
           while(i++ < k ){
                first = first.next;
               if(first == null){ // that means k > l. choose to return
                  first = head;
               }
           }
           second =head;
           while(first.next!=null){
               first=first.next;
               second=second.next;
           }
           //now second points to element at l-k
           first.next = head;
           ListNode nth=second.next;
           second.next = null;
           return nth;     
       }
    }
    

    Complexity Analysis

    • Time complexity : $$O(k)$$.
      To find k'th position, algorithm traverses k times. rest of the operations are constant time.

    Approach #2 Avoiding multiple traversals [Accepted]

    Algorithm

    Previous approach have $$O(k)$$ time complexity. When this $$k$$ is too large, the solution will fail to finish in expected time limits.
    In order to find $$k$$'th position, multiple times the list might traversed. However, those extra traversal can be avoided by checking the list $$length$$ and $$k$$ values. A large k'th value equal to length would have no effect on the list.
    Rotation the list by its length is equal to initial list. So, for large k values, only $$k~mod~length$$ many rotation is needed.

    Java

    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {        
            if(head == null || k ==0 )
                 return head;
            
            ListNode first;
            ListNode second;
            first=head;
            int i=0;
            while(i++ < k ){
                 first = first.next;
                if(first == null){ // that means k > l. choose to return
                   first = head;
                   int length = i;
                   i=0;
                   k=k%length;
                }
            }
            second =head;
            while(first.next!=null){
                first=first.next;
                second=second.next;
            }
            //now second points to element at l-k
            first.next = head;
            ListNode nth=second.next;
            second.next = null;
            return nth;     
        }
    }
    

    Complexity Analysis
    Algorithm traverse up to end of list which take $$n$$ operations then take $$k~mod~length$$ more steps which is smaller then $$n$$.
    So, time complexity is $$O(2n) = O(n)$$.


Log in to reply
 

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