leetCode ✏基础刷题之(61. Rotate List)
.
✏描述
给定一个链表，把链表中的每一个数都向右移动 k 位。其中 k 是非负数。图中给了很详细的每步变化。
✏题目实例
✏题目分析
先说下思路，其实整体只需要两步，第一步先将这个链表闭环。什么意思呢，拿 demo1 来说，本来节点5的 next 指向的是 null,现在把它变为 5->next=1。这样的话就形成了闭环。第二步当然就是计算新链表的头和尾分别是哪个节点(头结点的上一个节点一定是新链表的尾节点)，本质上就是在合适的地方截断这个闭环的链表，然后头尾相连。
新的链表头部位置必然在 n-k 处 (n是链表节点个数)，那尾结点就必然在 n-k-1 处，但是这样只考虑到 k
✏最终实现代码
/**
* 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==null) return null;
if($head->next==null) return $head;
$old_tail=$head;
$n=1;
//获取节点个数
while($old_tail->next !=null){
$old_tail=$old_tail->next;
$n++;
}
$old_tail->next=$head;
$new_tail=$head;
//获取尾结点
for($i=0;$i<$n-$k%$n-1;$i++){
$new_tail=$new_tail->next;
}
//头结点
$new_head=$new_tail->next;
//尾结点的next指向null
$new_tail->next=null;
return $new_head;
}
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)