061 - Rotate List

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.

Hide Tags

Linked List Two Pointers

Hide Similar Problems

(E) Rotate Array

 

找到需要断开的位置，把原来的头放在尾巴后面就好了。

注意 k 可能比链表长度大，所以需要求个长度然后求余。

 

/**
* 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(head)
        {
            ListNode* q = head;
            ListNode* e = head;
           
            int len=1;
            while(e->next)
                e = e->next, len++;
   
            k = len - (k%len);
            while(--k)
                q = q->next;
           
            e->next = head;
            head = q->next;
            q->next = NULL;
        }
        return head;
    }
};

8 ms.