当前位置： 面试刷题>> 旋转链表(经典算法150题)
### 题目描述
给定一个链表的头节点 `head`，链表的每个节点都包含一个整数值。现在需要将链表向右旋转 `k` 个位置，其中 `k` 是非负整数。旋转链表意味着将链表中的元素向右移动 `k` 个位置，其中尾部的元素将移动到链表的头部。如果 `k` 大于链表的长度，则旋转相当于旋转 `k` 模链表长度的次数。
例如，给定链表 `1->2->3->4->5` 和 `k = 2`，则旋转后的链表应该是 `4->5->1->2->3`。
### 示例代码
以下是使用 PHP、Python 和 JavaScript 编写的解决方案示例：
#### PHP
```php
val = $val;
$this->next = $next;
}
}
function rotateRight($head, $k) {
if ($head == null || $head->next == null || $k == 0) {
return $head;
}
$tail = $head;
$length = 1;
// 计算链表长度，并找到尾节点
while ($tail->next != null) {
$tail = $tail->next;
$length++;
}
// 处理 k 大于链表长度的情况
$k = $k % $length;
if ($k == 0) {
return $head;
}
// 将尾节点连接到头节点形成环
$tail->next = $head;
// 找到新的头节点的前一个节点
for ($i = 0; $i < $length - $k - 1; $i++) {
$head = $head->next;
}
// 断开环，形成新的链表
$newHead = $head->next;
$head->next = null;
return $newHead;
}
// 使用示例（需自行构建链表和调用函数）
?>
```
#### Python
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def rotateRight(head, k):
if not head or not head.next or k == 0:
return head
tail = head
length = 1
# 计算链表长度，并找到尾节点
while tail.next:
tail = tail.next
length += 1
# 处理 k 大于链表长度的情况
k = k % length
if k == 0:
return head
# 将尾节点连接到头节点形成环
tail.next = head
# 找到新的头节点的前一个节点
for _ in range(length - k - 1):
head = head.next
# 断开环，形成新的链表
new_head = head.next
head.next = None
return new_head
# 使用示例（需自行构建链表和调用函数）
```
#### JavaScript
```javascript
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function rotateRight(head, k) {
if (!head || !head.next || k === 0) {
return head;
}
let tail = head;
let length = 1;
// 计算链表长度，并找到尾节点
while (tail.next) {
tail = tail.next;
length++;
}
// 处理 k 大于链表长度的情况
k = k % length;
if (k === 0) {
return head;
}
// 将尾节点连接到头节点形成环
tail.next = head;
// 找到新的头节点的前一个节点
for (let i = 0; i < length - k - 1; i++) {
head = head.next;
}
// 断开环，形成新的链表
const newHead = head.next;
head.next = null;
return newHead;
}
// 使用示例（需自行构建链表和调用函数）
```
这些示例代码均提供了旋转链表的解决方案，可以根据需要进行适当的调整以符合特定的编码规范或测试要求。