LeetCode

Rotate List

2013.12.21 02:02

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Solution1:

　　My first solution is clumsy with O(n^2) time complexity (X_X), at least it proves that writing this blog is necessary. Because I wouldn't remember having written such poor codes, and force myself with a better solution, a solution that is decent enough to show you here. See Solution 2, please.

　　Time complexity is O(n^2), space complexity is O(1).

Accepted code:

// 2TLE, 1WA, 1AC
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head == nullptr){
            return head;
        }
        
        int i, len;
        ListNode *tail;
        ListNode *newhead;
        ListNode *ptr1, *ptr2;
        
        len = 0;
        ptr1 = head;
        while(ptr1 != nullptr){
            ptr1 = ptr1->next;
            ++len;
        }
        k = k % len;
        if(k == 0){
            return head;
        }
        
        tail = head;
        while(tail->next != nullptr){
            tail = tail->next;
        }
        // Make it a loop~
        tail->next = head;
        
        ptr1 = head;
        while(true){
            ptr2 = ptr1;
            for(i = 0; i <= k; ++i){
                ptr2 = ptr2->next;
            }
            if(ptr2 == head){
                // 1WA here, should be $ptr1, wrote $ptr2
                newhead = ptr1->next;
                ptr1->next = nullptr;
                break;
            }else{
                // 2TLE here, forgot to move $ptr1 forward
                ptr1 = ptr1->next;
            }
        }
        
        return newhead;
    }
};

Solution2:

　　To rotate the list right by k nodes, we'll need to know the location of 4 nodes: head, tail, the last kth, the last (k + 1)th.

　　The position of the nodes can be determined in O(n) time, after that we'll use O(1) time to alter the $next pointers to new direction.

　　Time complexity is O(n), space complexity is O(1).

Accepted code:

// 1AC, excellent
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if(nullptr == head){
            return head;
        }
        
        int len = 0;
        ListNode *p1 = nullptr, *p2 = nullptr, *tail = nullptr;
        
        // calculate the length of the list
        p1 = head;
        len = 0;
        while(p1 != nullptr){
            if(p1->next == nullptr){
                tail = p1;
            }
            ++len;
            p1 = p1->next;
        }
        if(tail == nullptr){
            // cannot possibly happen
            return nullptr;
        }
        
        // reduce k to k % len
        k = k % len;
        if(k == 0){
            return head;
        }
        
        // find the (k + 1)th node from the end
        p1 = p2 = head;
        for(int i = 0; i < k + 1; ++i){
            p1 = p1->next;
        }
        while(p1 != nullptr && p2 != nullptr){
            p1 = p1->next;
            p2 = p2->next;
        }
        
        p1 = head;
        head = p2->next;
        p2->next = nullptr;
        tail->next = p1;
        return head;
    }
};