Anyone solve the problem without counting the length of List?


  • 26
    E

    My solution has O(n) time complexity and O(1) memory.
    The basic idea is to connect the list into a circle. First, count the length of list while going through the list to find the end of it. Connect the tail to head. The problem asked to rotate k nodes, however, now the tail is at the end of the list and its difficult to move backward, so move (k - len) nodes along the list instead. "k = k % len" saves the unnecessary moves because rotate a list with length = len by len times doesn't change the list at all.

    ListNode *rotateRight(ListNode *head, int k) {
            if (head == NULL || head->next == NULL || k == 0) return head;
            int len = 1;
            ListNode *tail = head;
    
            /* find the end of list */
            while (tail->next != NULL) {
                tail = tail->next;
                len++;
            }
    
            /* form a circle */
            tail->next = head;
            k = k % len;
            for (int i = 0; i < len - k; i++) {
                tail = tail->next;
            }
            head = tail->next;
            tail->next = NULL;
            return head;
        }

  • 19
    S

    Yes, you can use a two pointer technique where the 'fast' pointer is always k nodes ahead of 'slow'. By the time 'fast' reaches the last node, 'slow' must be pointing to the (k+1)th nodes from backwards, then you can simply detach slow->next from slow, then set fast->next to head, and you are done.


  • 1
    E

    LOL. This is what I'm trying to do right now. But when k is bigger than the length of list, i have to move the 'fast' pointer to the beginning of the list and do some adjustment to the code. I'll post this version of solution once i figured it out. Thanks for your tips! :)


  • 12
    J
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || head.next == null || n == 0) {
             return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode newHead;
        for (int i = 0; i < n; i++) {
            if (fast.next == null) {
                fast = head;
            } else {
                fast = fast.next;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        fast.next = head;
        newHead = slow.next;
        slow.next = null;
        return newHead;
    }
    

    This is my solution without counting the length. The trick is that when n > length, you put fast back to head. :)


  • 6
    A

    If for example the length of the list is 3 and n is 999999999, then your algorithm is very inefficient.
    In other words your algorithm time complexity is O(max(n,length-of-list)) and the complexity of the algorithm with length counting is O(length-of-list). When n is much larger than the list length then the O(max(n,length-of-list)) complexity is very poor.


  • 0
    Z

    When n is larger than the length. Make n %= length


  • 1
    J

    I understand your concern, but the reason I showed this solution here is to show how to solve this question without counting the length of the list.


  • 1
    Y

    I think count the length n of list is necessary because that ensures that you can solve this problem in O(n) time by doing k=k%n. Just connect the head and tail, keep iterating k steps is not feasible.


  • 0
    L

    Agree with yuyibestman. If k >> n, it would be better count the length first.


  • 0
    T

    Even there is no a "len" variable but you actually have gone through the whole length of the list,which is same as counting the length.


  • 0
    J

    As @erichsueh said, if k = 2n - 1, it may need two loops. But it is still a good idea.


  • 0
    J

    Just as another illustration (good for long lists though the length is used):

    class Solution {
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            if (head == NULL || k <= 0) return head;
            ListNode* newTail = head;
            ListNode* tail = head;
            int n = 1;  // It is useful when k > length.
            while (tail->next != NULL) {
                tail = tail->next;
                if (n > k) newTail = newTail->next;  // time to move
                n++;
            }
            if (k % n == 0) return head;
            if (k > n) {  // Ouch, k is too large so newTail did not move.
                for (int i = n - (k % n) - 1; i > 0; i--) newTail = newTail->next;
            }
            ListNode* newHead = newTail->next;
            newTail->next = NULL;
            tail->next = head;
            return newHead;
        }
    };
    

  • 0
    A

    I think that the solution in the answer will not work if slow.next is null after the second loop.


  • 0
    P

    '''
    class Solution {
    public:
    ListNode* rotateRight(ListNode* head, int k) {
    if(head==NULL)
    return head;
    int count = 0, len = 0;
    ListNode *p1 = findPosition(head, k, count, len);
    if(p1->next==NULL){
    return head;
    }
    else{
    ListNode *p2 = p1->next;
    p1->next = NULL;
    ListNode *p3 = p2;
    while(p3->next!=NULL)
    p3 = p3->next;
    p3->next = head;
    return p2;
    }
    }

    ListNode* findPosition(ListNode* head, int &k, int &count, int &len){
        if(head == NULL){
            k = k%len;
            return head;
        }
        len++;
        ListNode *res = findPosition(head->next, k, count, len);
        if(k == count++)
            return head;
        return res;
    }
    

    };

    '''


  • 0
    K

    This is the python logic.
    it works for low k's but it gives memory error when k is big (600000000)

    class Solution(object):
        def rotateRight(self, head, k):
            if not head or not head.next:
                return head
            fast = head
            slow = head
            for i in range(k):
                if fast.next:
                    fast = fast.next
                else:
                    fast = head
            while fast.next:
                fast = fast.next
                slow = slow.next
            fast.next = head
            head = slow.next
            slow.next = None
            return head
    

  • 0
    C

    easy to comprehend, thx


  • 0
    J

    Combine the ideas of counting the length then modify k to k%n when k > n and not counting the length when there is no need for k < n. The runtime does not improve for the testcases, so just share the idea not the solution.

    ListNode* rotateRight(ListNode* head, int k) {
            if(head == NULL || head->next == NULL) return head;
            // use pointer to pointer for easily rotate list
            ListNode **slow = &head, **fast = &head;
            for(int i = 0; i < k; ++i){
                fast = &((*fast)->next);
                if(*fast == NULL)
                {   // when the first time fast pointer reach the end, we know k at least n (length n = i + 1), so reset fast pointer to head and modify the loop control to k%length, so that this loop will run not more than twice.
                    unsigned length = i+1;
                    fast = &head;
                    i = -1;
                    k %= length;
                }
            }
            // if we out of the loop with fast pointer = head, we know k%length = 0, so there is no need to rotate, just return head
            if((*fast) == head) return head;
            // the left move is the same with others
            while((*fast)!= NULL) {
                fast = &((*fast)->next);
                slow = &((*slow)->next);
            }
            *fast= head;
            head = *slow;
            *slow = NULL;
            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

    I'm agree with @carterbao . And here is my python solution.

    class Solution(object):
        def rotateRight(self, head, k):        
            if k == 0 or not head:
                return head
            count = 1
            left = right = head
            while right.next and count <= k: # make right go k steps first
                count += 1
                right = right.next
            if count <= k: # if k is larger the the length, make new k
                return self.rotateRight(head, k % count)
            while right.next:
                right = right.next
                left = left.next
            sentry = left.next
            right.next = head
            left.next = None
            return sentry
    

  • 1
    Y

    @jiaming2 said in Anyone solve the problem without counting the length of List?:

    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || head.next == null || n == 0) {
             return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode newHead;
        for (int i = 0; i < n; i++) {
            if (fast.next == null) {
                fast = head;
            } else {
                fast = fast.next;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        fast.next = head;
        newHead = slow.next;
        slow.next = null;
        return newHead;
    }
    

    This is my solution without counting the length. The trick is that when n > length, you put fast back to head. :)

    It's a O(k) solution, it's not optimized when k is large. Here is my solution:

    class Solution(object):
        def rotateRight(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            if head is None:
                return
            dis=0
            node=head
            while node.next and dis<k:
                node=node.next
                dis+=1
            if dis==k:
                tail=head
                while node.next:
                    node=node.next
                    tail=tail.next
                node.next=head
                head=tail.next
                tail.next=None
                return head
            else:
                return self.rotateRight(head,k%(dis+1))
    

Log in to reply
 

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