首页 > 代码库 > [leetcode] Rotate List

[leetcode] Rotate List

问题描述:

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.

基本思想:

本题需要考虑k 大于链表长度的情况。所以链表需要右移的数字是 k%size。


代码:

 ListNode *rotateRight(ListNode *head, int k) { //C++
        if(head ==NULL || k == 0) 
            return head;
        
        ListNode* tmp = head;
        int size = 1;
        while(tmp->next != NULL)
        {
            size++;
            tmp = tmp->next;   
        }
        ListNode* final = tmp;
        
        int shift = k%size;
        if(shift == 0)
            return head;
        
        ListNode* fast = head;
        ListNode* pre = head;
        for(int i = 0; i< size-shift; i++)
        {
            pre = fast;
            fast = fast->next;
            
        }
        final->next = head;
        head = fast;
        pre->next = NULL;
            
        return head;
    }
};


[leetcode] Rotate List