NO CODING NO LIFE: Lintcode: Rotate List

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

Have you met this question in a real interview?

Yes

Example

Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.

Tags Expand

Initial solution:(split the rotated part and joint to the beginning)
Traditional two pointers problem;
Set two pointer at a distance of k, move to the end and cut the part between two pointers, then connect it to the beginning of the linked list.
Note the situation when k = 0
Time: O(n)
Space: O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head: the list
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ListNode *rotateRight(ListNode *head, int k) {
        // write your code here
        if(head == NULL) return NULL;
        int len = 0;
        ListNode *left, *right;
        right = left = head;
        //when k >= linkedlist length
        ListNode *temp = head;
        while(temp){
            temp = temp->next;
            len++;
        }
        k = k % len;
        for(int i = 0; i < k; i++){
            right = right->next;
        }
        while(right->next != NULL){
            left = left->next;
            right = right->next;
        }
        //when k == 0
        if(left == right) return head;
        right->next = head;
        head = left->next;
        left->next = NULL;
        return head;
    }
};

Lintcode second

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 //4:21 -- 4:36
class Solution {
public:
    /**
     * @param head: the list
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ListNode *rotateRight(ListNode *head, int k) {
        // write your code here
        if(head == NULL) return head;
        ListNode *slow, *fast;
        slow = fast = head;
        for(int i = 0; i < k; i++){
            fast = fast->next;
            if(fast == NULL) fast = head;
        }
        ListNode *prev_slow, *prev_fast;
        while(fast){
            prev_fast = fast;
            fast = fast->next;
            prev_slow = slow;
            slow = slow->next;
        }
        if(slow == NULL) return head;
        prev_fast->next = head;
        prev_slow->next = NULL;
        return slow;
    }
};

NO CODING NO LIFE

2015年9月1日星期二

Lintcode: Rotate List

没有评论:

发表评论