Rotate Linked List in O(N) time and constant space describing all acenarios


  • 0
    K
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if(head ==null || head.next ==null || k==0)
            {
                return head;
            }
            
            
            int size = 0;
            ListNode ActualHead = head;
            while(head!=null)
            {
                size++;
                head = head.next;
            }
            if(size == k)
            {
                return ActualHead;
            }
            if(size<k)
            {
                k = k%size;
                if(k==0)
                {
                    return ActualHead;
                }
            }
            
            int count = 1;
            
            ListNode temp = ActualHead;
            ListNode t = null;
            
          
            while(temp!=null)
            {
              
                if(count==size-k)
                {
                     t = temp.next;
                    temp.next= null;
                    
                    break;
                }
                count++;
                temp = temp.next;
            }
           
            ListNode ans = t;
            while(t!=null)
            {
                
                if(t.next==null)
                {
                    t.next = ActualHead;
                    break;
                }
                t = t.next;
            }
            
            return ans;
            
            
        }
    }
    

Log in to reply
 

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