LeetCode 第 61 题旋转链表

简介: LeetCode 第 61 题旋转链表

题目


旋转链表


给你一个链表的头节点 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


题解


解题分析


解题思路


  1. 如果链表的长度为 n, 当我们向右移动的次数 k >= n 时,我们只需要向右移动 k % n 次即可,因为 n 每次移动都会让链表回到原点,新的链表的起点 (n - 1) - (k % n) 个节点(从 0 开始)。


  1. 这样,我们可以先把链表连接成环,然后将指定位置断开。


  1. 具体代码中,我们先计算出链表的长度 n ,并且找到该链表的末尾节点,将其与头部节点相连。这样就得到一个闭合为环的链表。然后我们从新找到新链表的最后一个节点(即原链表的 (n-1)- (k %n) 个节点),将当前闭合为环的链表断开,即可以得到结果。


  1. 有一个可以优化的点就是当 k % n == 0 的时候,新的链表和原链表相同,我们无需做任何处理。


复杂度


  • 时间复杂度 O(N)


  • 空间复杂度 O(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) {
        // 1. 边界值处理
        if (head == null  || k == 0 || head.next == null) {
            return head;
        }
        // 2. 链表长度计算
        int n = 1;
        // 3. iter 指针指向尾节点
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        // 4. 如果 k > n 那么势必要旋转多圈,那么我们只需要旋转有效的 <n 此即可
        int add = n - k % n ;
        // 5. 特殊情况,旋转到原地
        if (add == n) {
            return head;    
        }
        // 6. 尾节点指向头节点,形成环
        iter.next = head;
        // 7. 实际旋转
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        // 8. 去除环
        iter.next = null;
        return ret;
    }
}


提交后反馈结果如下:


网络异常,图片无法展示
|


参考信息



相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
38 1
|
2月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
52 0
Leetcode第21题(合并两个有序链表)
|
2月前
|
机器学习/深度学习
Leetcode第48题(旋转图像)
这篇文章介绍了LeetCode第48题“旋转图像”的解题方法,通过原地修改二维矩阵实现图像的顺时针旋转90度。
33 0
Leetcode第48题(旋转图像)
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
25 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
26 0
LeetCode第二十四题(两两交换链表中的节点)
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
46 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
2月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
96 0
|
2月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
23 0
|
2月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
18 0
|
2月前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
13 0