What to do when k is greater than size of list ?


  • 26
    R

    i am not getting that what i should do when K is greater than size of the list.


  • 47

    Let's start with an example.

    Given [0,1,2], rotate 1 steps to the right -> [2,0,1].

    Given [0,1,2], rotate 2 steps to the right -> [1,2,0].

    Given [0,1,2], rotate 3 steps to the right -> [0,1,2].

    Given [0,1,2], rotate 4 steps to the right -> [2,0,1].

    So, no matter how big K, the number of steps is, the result is always the same as rotating K % n steps to the right.


  • 1
    I

    What does it mean by "rotate to the right" ? I guess it's more like to say "rotate the last node from the left"


  • 1
    W

    Thanks 1337. This is clear. You should use this as the "problem statement".


  • 1
    L

    I also get stuck in such case, and finally I got it over. In such case , k = k % size;


  • 3
    D

    This is my code, Given two pointers, one is faster than the other by k steps ,when k>n I just reset from head.

     ListNode *rotateRight(ListNode *head, int k) {
        if(head==NULL)
            return NULL;
        ListNode* slow=head;
        ListNode* fast=head;
        int cnt=0;
        while(cnt<k)
        {
           if(!fast)fast=head;
           fast=fast->next;
           cnt++;
        }
        if(fast==NULL) return head;
        while(fast->next){
            fast=fast->next;
            slow=slow->next;
        }
        fast->next=head;
        head=slow->next;
        slow->next=NULL;
        return head;  
      }
    

  • 1
    Z

    if k is very big,your first while may cost much time,why not first find the lenth of the list,define it len,and then the we only need rotate k % len;


  • 1
    H

    when k is larger than length, k can be replaced by k % length. Or your first while loop will cost a really long time when k is really big.


  • 0
    H

    {
    class Solution {
    public:
    ListNode* rotateRight(ListNode* head, int k) {
    if(!head) return NULL;
    ListNode *p=head;
    int i=0;
    while(i!=k&&p!=NULL){
    p=p->next;
    i++;
    }
    if(p!=NULL){
    ListNode *q=head;
    while(p->next!=NULL){
    p=p->next;
    q=q->next;
    }
    p->next=head;
    head=q->next;
    q->next=NULL;
    return head;

        }
        else{
            k%=i;
            return rotateRight(head,k);
        }
        
    }
    

    }; // if k is larger than length, k%=i return return rotateRight(head,k);
    }


  • 0

    @rforritz I think if k > list's size, what we should do is rotate the list with k % lists' size steps.


  • 0
    W

    @dingou666 Time Limit Exceeded


  • 0
    T
    This post is deleted!

  • 0
    C

    Thanks for your explanation !


  • 0
    W

    @introom rotate could be better explained as "shift to right".


Log in to reply
 

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