Rotate List

LeetCode #61

Description:

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

Example:

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

Idea:

先遍历一遍，得出链表长度 len，注意 k 可能大于 len，因此令 k% = len。将尾节点 next 指针 指向首节点，形成一个环，接着往后跑 len − k 步，从这里断开，就是要求的结果了.

Code:

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == NULL) return head;

        int len=0;
        ListNode *curr = head;
        while(curr!=NULL){
            curr = curr->next;
            len++;
        }

        k = k%len;
        if(k==0) return head;

        curr=head;
        ListNode *pre=head;

        int step=0;
        while(curr->next!=NULL){
            curr = curr->next;
            step++;
            if(step>k){ // curr first move k steps, then pre moves
                pre=pre->next;
            }
        }
        curr->next=head;
        head=pre->next;
        pre->next=NULL;
        return head;

    }
};