# 0061. 旋转链表

## 题目地址(61. 旋转链表)

<https://leetcode-cn.com/problems/rotate-list/>

## 题目描述

```
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
```

## 快慢指针法

### 前置知识

* 求单链表的倒数第 N 个节点

### 思路一

1. 采用快慢指
2. 快指针与慢指针都以每步一个节点的速度向后遍历
3. 快指针比慢指针先走 N 步
4. 当快指针到达终点时，慢指针正好是倒数第 N 个节点

### 思路一代码

* 伪代码

```javascript
快指针 = head;
慢指针 = head;
while (快指针.next) {
  if (N-- <= 0) {
    慢指针 = 慢指针.next;
  }
  快指针 = 快指针.next;
}
```

* 语言支持: JS

JS Code:

```javascript
let slow = (fast = head);
while (fast.next) {
  if (k-- <= 0) {
    slow = slow.next;
  }
  fast = fast.next;
}
```

### 思路二

1. 获取单链表的倒数第 N + 1 与倒数第 N 个节点
2. 将倒数第 N + 1 个节点的 next 指向 null
3. 将链表尾节点的 next 指向 head
4. 返回倒数第 N 个节点

例如链表 A -> B -> C -> D -> E 右移 2 位，依照上述步骤为：

1. 获取节点 C 与 D
2. A -> B -> C -> null, D -> E
3. D -> E -> A -> B -> C -> nul
4. 返回节点 D

> 注意：假如链表节点长度为 len，\
> 则右移 K 位与右移动 k % len 的效果是一样的\
> 就像是长度为 1000 米的环形跑道，\
> 你跑 1100 米与跑 100 米到达的是同一个地点

### 思路二代码

* 伪代码

```javascript
  获取链表的长度
  k = k % 链表的长度
  获取倒数第k + 1,倒数第K个节点与链表尾节点
  倒数第k + 1个节点.next = null
  链表尾节点.next = head
  return 倒数第k个节点
```

* 语言支持: JS, JAVA, Python, CPP, Go, PHP

JS Code:

```javascript
var rotateRight = function (head, k) {
  if (!head || !head.next) return head;
  let count = 0,
    now = head;
  while (now) {
    now = now.next;
    count++;
  }
  k = k % count;
  let slow = (fast = head);
  while (fast.next) {
    if (k-- <= 0) {
      slow = slow.next;
    }
    fast = fast.next;
  }
  fast.next = head;
  let res = slow.next;
  slow.next = null;
  return res;
};
```

JAVA Code:

```java
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;
        int count = 0;
        ListNode now = head;
        while(now != null){
            now = now.next;
            count++;
        }
        k = k % count;
        ListNode slow = head, fast = head;
        while(fast.next != null){
            if(k-- <= 0){
                slow = slow.next;
            }
            fast = fast.next;
        }
        fast.next = head;
        ListNode res = slow.next;
        slow.next = null;
        return res;
    }
}
```

Python Code:

```python
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        # 双指针
        if head:
            p1 = head
            p2 = head
            count = 1
            i = 0
            while i < k:
                if p2.next:
                    count += 1
                    p2 = p2.next
                else:
                    k = k % count
                    i = -1
                    p2 = head
                i += 1

            while p2.next:
                p1 = p1.next
                p2 = p2.next

            if p1.next:
                tmp = p1.next
            else:
                return head
            p1.next = None
            p2.next = head
            return tmp
```

CPP Code:

```cpp
class Solution {
    int getLength(ListNode *head) {
        int len = 0;
        for (; head; head = head->next, ++len);
        return len;
    }
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return NULL;
        int len = getLength(head);
        k %= len;
        if (k == 0) return head;
        auto p = head, q = head;
        while (k--) q = q->next;
        while (q->next) {
            p = p->next;
            q = q->next;
        }
        auto h = p->next;
        q->next = head;
        p->next = NULL;
        return h;
    }
};
```

Go Code:

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    n := 0
    p := head
    for p != nil {
        n++
        p = p.Next
    }
    k = k % n
    // p 为快指针, q 为慢指针
    p = head
    q := head
    for p.Next!=nil {
        p = p.Next
        if k>0 {
            k--
        } else {
            q = q.Next
        }
    }
    // 更新指针
    p.Next = head
    head = q.Next
    q.Next = nil

    return head
}
```

PHP Code:

```php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function rotateRight($head, $k)
    {
        if (!$head || !$head->next) return $head;

        $p = $head;
        $n = 0;
        while ($p) {
            $n++;
            $p = $p->next;
        }
        $k = $k % $n;
        $p = $q = $head; // $p 快指针; $q 慢指针
        while ($p->next) {
            $p = $p->next;
            if ($k > 0) $k--;
            else $q = $q->next;
        }
        $p->next = $head;
        $head = $q->next;
        $q->next = null;

        return $head;
    }
}
```

**复杂度分析**

* 时间复杂度：节点最多只遍历两遍，时间复杂度为$O(N)$
* 空间复杂度：未使用额外的空间，空间复杂度$O(1)$


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/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.