给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
示例 1:
输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]
示例 2:
输入:head = [0,1,2], k = 4
输出:[2,0,1]
提示:
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/rotate-list
(1)双指针
详细分析过程见下面代码中的注释。
//思路1————双指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
//考虑特殊情况
if (k == 0 || head == null || head.next == null) {
return head;
}
//计算链表长度
int length = 0;
ListNode aux = head;
while (aux != null) {
aux = aux.next;
length++;
}
// 当 k > length 时,其旋转结果与 k = k % length 一样
k = k % length;
if (k == 0) {
// k % length 如果等于 0,则说明 length 是 k 的整数倍,旋转之后结果与原来相同,故直接返回 head
return head;
}
/*
设 n = length
V1 -> V2 -> ... -> V(n-k-1) -> V(n-k) -> ... -> Vn -> null
将链表每个节点向右移动 k 个位置之后,得到:
V(n-k) -> ... -> Vn -> V1 -> V2 -> ... -> V(n-k-1) -> null
所以只需要先找到找到节点 V(n-k-1)、V(n-k) 以及 Vn,然后令
V(n-k-1).next = null
Vn.next = V1(即head)
最后返回 V(n-k) 即可
V(n-k-1)、V(n-k) 以及 Vn 分别对应下面代码中的 lastNode、newHead 和最后一个while循环结束后的 aux
*/
aux = head;
ListNode lastNode = head;
int tmp = length - k;
while (tmp > 0) {
aux = aux.next;
if (tmp != 1) {
lastNode = lastNode.next;
}
tmp--;
}
lastNode.next = null;
ListNode newHead = aux;
while (aux.next != null) {
aux = aux.next;
}
aux.next = head;
return newHead;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_43004044/article/details/125633078
内容来源于网络,如有侵权,请联系作者删除!