现在的位置: 首页 > 综合 > 正文

LeetCode——Rotate List

2014年11月09日 ⁄ 综合 ⁄ 共 731字 ⁄ 字号 评论关闭

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.

»
Solve this problem

注意一点,K可能非常大,比链表的长度大得多,但是因为是循环右移,所以实际上只要循环右移K%Length位(Length为链表长度)。

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL || head->next == NULL || k == 0) {
            return head;
        }
        
        int length = 0;
        ListNode *ptr = head, *tail = head;
        while (ptr != NULL) {
            length++;
            tail = ptr;
            ptr = ptr->next; 
        }
        k %= length;
        
        ptr = head;
        for (int i = 0; i < length - k - 1; i++) {
            ptr = ptr-> next;
        }
        
        tail->next = head;
        head = ptr->next;
        ptr->next = NULL;
        
        return head;
    }
};

抱歉!评论已关闭.