# 61. Rotate List

## problem description

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

**Example 1:**

```
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
```

**Example 2:**

```
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
```

## algorithm thought

可以看到其实就是将链表倒数第k个位置截断，然后拼接到前面。知道这个意思之后，就只需要考虑如果k大于size的问题了。如果k等于size，链表长度不变，这就很明显，我们可以令k=k%size。最后截断链表即可

## code

```cpp
/**
 * 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==NULL)
            return head;
        int size=1;
        ListNode* tail=head;
        while(tail->next){
            size++;
            tail=tail->next;
        }
        if(size==1)
            return head;
        k=k%size;
        if(k==0)
            return head;
        k=size-k-1;
        ListNode* pre=head;
        ListNode* cur=head->next;
        while(k--){
            pre=pre->next;
            cur=cur->next;
        }
        pre->next=NULL;
        tail->next=head;
        return cur;
    }
};
```

## algorithm analysis

开始算法得到链表的size，时间复杂度O(n)。然后找到倒数第k个节点，最后


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/61.-rotate-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.