My clean C++ code, quite standard (find tail and reconnect the list)


  • 105
    D

    There is no trick for this problem. Some people used slow/fast pointers to find the tail node but I don't see the benefit (in the sense that it doesn't reduce the pointer move op) to do so. So I just used one loop to find the length first.

    class Solution {
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            if(!head) return head;
            
            int len=1; // number of nodes
            ListNode *newH, *tail;
            newH=tail=head;
            
            while(tail->next)  // get the number of nodes in the list
            {
                tail = tail->next;
                len++;
            }
            tail->next = head; // circle the link
    
            if(k %= len) 
            {
                for(auto i=0; i<len-k; i++) tail = tail->next; // the tail node is the (len-k)-th node (1st node is head)
            }
            newH = tail->next; 
            tail->next = NULL;
            return newH;
        }
    };

  • 0
    C

    so good!i like it!


  • 2

    Came up a solution almost the same as yours so just share here :)

    The difference is we don't need to make the circle when k %= length equals 0

    /**
     * Memo: Make the list into a circle if we need to rotate, then rotate to the needed location and break the circle.
     * Complex: O(n)
     * Runtime: 168ms
     * Tests: 230 test cases passed
     * Rank: S
     * Updated: 2015-06-18
     */
    var rotateRight = function(head, k) {
        if (!head || !head.next) return head; // no need to rotate if the list is empty or has only one element
    
        var length = 1;
        var tail = head;
        while (tail.next) {
            length++;
            tail = tail.next;
        }
    
        var newHead = head;
        if (k %= length) {
            tail.next = head; // make a full circle
            for (var i = 0; i < length - k; i++) tail = tail.next; // move to previous node before breaking point
            newHead = tail.next;
            tail.next = null; // break the circle
        }
        return newHead;
    };
    

  • 7
    F

    This is my solution. The difference is, when k <= lens, NO need to traverse the lists twice! Only once!
    The time consuming is 8ms.

    class Solution {
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            if(!k || !head || !head->next)
                return head;
            ListNode *fast = head;
            int lens = 1;
            while(k--)
            {
                if(fast->next)
                {
                    fast = fast->next;
                    lens ++;
                }
                else
                {
                    fast = head;
                    k %= lens;
                }
            }
            if(fast == head)
                return head;
            ListNode *slow = head;
            while(fast->next)
            {
                fast = fast->next;
                slow = slow->next;
            }
            ListNode *newhead = slow->next;
            slow->next = NULL;
            fast->next = head;
            return newhead;
        }
    };

  • 0
    R

    awesome, this is so clever.


  • 0
    P

    Clever idea!


  • 0

    Good solution! It is really clever to circular the link :-)


  • 1

    The following code is really clever :-)

    fast = head;
    k %= lens; 

  • 10
    L

    Nice idea. thanks for sharing.
    my solution based on your idea.

    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) return head;
        ListNode *cur = head;
        int len = 1;
        while (cur->next && ++len) cur = cur->next;
        cur->next = head;
        k = len - k % len;
        while (k--) cur = cur->next;
        head = cur->next;
        cur->next = nullptr;
       return head; 
    }

  • 0
    Z

    clever circle link!!


  • 0
    X
    This post is deleted!

  • 0
    D

    When the len is big and big and the k is so small ie.. 1,2,3... , your method will not be efficient I think.


  • 0
    D

    What a coincidence! My solution is same as yours.
    class Solution {
    public:

    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return NULL;
        int len = 1;
        ListNode *p = head;
        while (p->next) {
            p = p->next;
            len++;
        }
        p->next = head;
        k %= len;
        while (len>k) {
            p = p->next;
            len--;
        }
        head = p->next;
        p->next = NULL;
        return head;
    }
    

    };


  • 0
    C

    JavaScript:

    var rotateRight = function(head, k) {
      if (!head) {
        return head;
      }
    
      var len = 1;
      var newHead = new ListNode();
      var tail = new ListNode();
    
      newHead = tail = head;
    
      while (tail.next) {
        tail = tail.next;
        len++;
      }
    
      k %= len;
      tail.next = head;
    
      if (k) {
        for (var i = 0; i < len - k; i++) {
          tail = tail.next;
        }
      }
    
      newHead = tail.next;
      tail.next = null;
      return newHead;
    };
    

  • 0
    S

    @dong.wang.1694
    awesome! This method don't move the value in the memory but only the pointer of the list.


  • 0
    B

    @SwenZhai , is there any problem related to Linked-list solved by changing the value of the list node ?


  • 0
    K

    Python translation

    class Solution(object):
        def rotateRight(self, head, k):
            if not head or not head.next:
                return head
            current = head
            len = 1
            while current.next:
                current = current.next
                len += 1
            current.next = head
            k = k % len
            print(k)
            print(len)
            for i in range(len-k):
                current = current.next
            head = current.next
            current.next = None
            return head
    

  • 0

    Here is my solution, which doesn't need to count the length of the list first. Just use faster pointer and slower pointer method, when moving the faster pointer and k is larger than the length of the list, make k = k%length and move from head again. So even if k is far larger than list length, we will go through the list for no more than twice

    ListNode* rotateRight(ListNode* head, int k) {
            if(!head || k==0) return head;
            ListNode* p1 = head, *p2 = head;
            for(int i=0;i<k;i++){ // move the faster pointer for k steps first
                if(p1->next) p1 = p1->next;
                else{
                    k = k%(i+1);//if k is greater than the length of the list, make k = k%length
                    i = -1; // and count from the beginning again
                    p1 = head; // move p1 to head and count again
                }
            }
            while(p1->next!=NULL){
                p1 = p1->next;
                p2 = p2->next;
            }
            p1->next = head;
            head = p2->next;
            p2->next = NULL;
            return head;
        }
    

  • 0
    W

    @dong.wang.1694 The fast and slow pointer method has some advantages that is not so obvious. It is one-shot traverse. Think about the situation when device is lack of memory. The time consumption is mainly related to data transfer from disk to memory which means One-shot traverse is definitely faster than two or more traverses. In this way, two pointers method seems to outperform your algorithm. However, under the hypothesis that RAM is sufficient, two approaches are almost equivalent. I prefer your concise solution.


  • 0

    C++ Version

    class Solution {
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            if (!head) return NULL;
            int len = 1;
            ListNode *p = head;
            while (p->next) {
                ++len;
                p = p->next;
            }
            p->next = head;
            k = len - k % len;
            while (k--) p = p->next;
            head = p->next;
            p->next = NULL;
            return head;
        }
    };
    

Log in to reply
 

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