给定一个链表,旋转链表,将链表每个节点向右移动 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
因为移动 k 个位置,k 有可能比当前链表的长度大,也有可能比当前链表的长度小。如果比当前链表长度大,那么就会执行好圈的旋转。因此要求最终的需要旋转的节点个数,就使用 k % 链表长度。
一开始它的链表结构如下:
然后我们将它连成一个环,即将 5 的节点指向第一个节点 1。
当 k 等于 2 的时候,我们就是要将指针移动 链表长度 5 - (2 % 5 ) 个位置:
我们可以看到,按要求 k = 2 的时候,我们最终的末端节点就是 3。因为它是一个环,所以 3 作为末端节点,那么它的下一个节点 4 就是首节点。
综上,我们这个题目的核心就是找一个旋转链表的末节点。它和 k 的关系就是链表的长度 - k 的值。
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null){
return head;
}
// 构造一个环
ListNode old_tail = head;
int n;
for(n = 1; old_tail.next != null; n++){
old_tail = old_tail.next;
}
//将首尾链接起来,变成一个环
old_tail.next = head;
//定义一个新的节点头,初始值为 head
ListNode new_tail = head;
//因为是一个环,所以我们可以取长度 k % n 的模值,将需要移动的环排除掉
int needMoveCount = n - k % n;
for (int i = 0; i < needMoveCount - 1; i++){
new_tail = new_tail.next;
}
//遍历到新的节点的末尾,因为是一个环
ListNode new_head = new_tail.next;
new_tail.next = null;
return new_head;
}
}
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 构造一个环
var old_tail *ListNode = head
n := 0
for n = 1; old_tail.Next != nil; n++ {
old_tail = old_tail.Next
}
//将首尾链接起来,变成一个环
old_tail.Next = head
//定义一个新的节点头,初始值为 head
var new_tail *ListNode = head
//因为是一个环,所以我们可以取长度 k % n 的模值,将需要移动的环排除掉
needMoveCount := n - k % n
for i := 0; i < needMoveCount - 1; i++{
new_tail = new_tail.Next
}
//遍历到新的节点的末尾
var new_head *ListNode = new_tail.Next
new_tail.Next = nil
return new_head
}