首页 > 其他分享 >【力扣】旋转链表

【力扣】旋转链表

时间:2024-02-24 22:56:07浏览次数:28  
标签:力扣 head index1 ListNode next 链表 index2 旋转

题目描述

image

思路

首先用双指针法向后移动,分别获取链表的最后一个结点和倒数第k的结点,再把这部分连接到链表的头部即可,这部分的操作并不难。

但是实际这样写了之后就会发现,如果链表的长度小于k的话,这样的操作就是行不通的,需要对这种情况进行特殊处理。

但是在处理过程中发现这个操作有这样的特点:当链表长度leng小于k时,将链表旋转k个位置其实就相当于把链表旋转k%leng个位置,即余数个位置。

另外还发现:在链表长度为0、1,以及k为0这些情况下,都不需要进行任何操作。
于是得出下面的代码:

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
	//进行特殊情况的处理
        if(head == nullptr || k == 0 ){
            return head;
        }
        if(head -> next == nullptr){
            return head; 
        }
		
        ListNode* Dummy = new ListNode(0,head);
        ListNode* index1 = new ListNode();
        ListNode* index2 = new ListNode();
        index1 = Dummy;
        index2 = Dummy;
        int i = k;
        int length = 0;
        while(i--){
            index2 = index2 -> next;
            if(index2 -> next == nullptr){
                length = k-i;
                break;
		//这是链表长度<=k的情况
            }
            
        }
        if( length){
            return rotateRight(head, k%length);
	//这样就把长度小于k的情况转化为了下面的一般情况
	//因为k除以链表长度的余数一定是小于k的,这样就归到了一般情况里去
        }
		
	//一般情况,把后面k个结点连接到链表头部
        while(index2 -> next != nullptr){
            index1 = index1 -> next;
            index2 = index2 -> next;
        }
        index2 -> next = Dummy -> next;
        ListNode* result = index1 -> next;
        index1 -> next = nullptr;
        return result;                
    }
};

同时这个思路的时间复杂度不会超过链表的长度,时间上效率也很好。
image
官方题解:
image

标签:力扣,head,index1,ListNode,next,链表,index2,旋转
From: https://www.cnblogs.com/satsuki26681534/p/18031764

相关文章

  • 【力扣刷题】合并两个有序链表
    题目描述分析这道题实际的解法是要通过递归来写,由于链表的特性:链表的任何一个子表都是链表。所以很多链表的算法用递归来写会非常简便。这里先尝试着写一下非递归的算法,再写一遍递归的算法。非递归:classSolution{public://voidInsert(ListNode*node1,ListNode*n......
  • 《原神》那维莱特自动旋转的Python脚本
    实现代码importtimeimportpydirectinputimportkeyboardif__name__=='__main__':revolve=FalsewhileTrue:time.sleep(0.1)ifkeyboard.is_pressed(','):revolve=Trueprint('Revol......
  • 代码随想录算法训练营day03 | leetcode 203. 移除链表元素、707. 设计链表、206. 反转
    目录题目链接:203.移除链表元素-简单题目链接:707.设计链表-中等题目链接:206.反转链表-简单题目链接:203.移除链表元素-简单题目描述:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6......
  • 随机旋转岩石工具
    思路:制作一个石头模型并对其碰撞进行自动凸包,放入蓝图中,通过蓝图中的构造脚本进行随机旋转,即可实现石块放置时的旋转效果;演示操作1.创建石头模型使用BSP工具进行顶点编辑添加材质后转成静态网格体对模型进行自动凸包碰撞2.蓝图中控制石块的随机旋转和缩放为了方便控制缩......
  • 链表
    链表特性通过每个结点记录之后或之前结点的值,那么就可以知道所有结点的排列顺序。插入如果要在链表中插入一个元素。那么就可以将前面的元素的后缀(指的是之后结点的值)改成插入的元素,插入元素的后缀顶上前面元素的后缀。voidinsret(intx,inty){ nxet[y]=next[x]; next[......
  • 力扣递归之 236. 二叉树的最近公共祖先
    给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个节点p、q,最近公共祖先表示为一个节点x,满足x是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。” 示例1:输入:root=[3,5,1,6,2,0,8,null,n......
  • 力扣 dfs之 437. 路径总和 III
    给定一个二叉树的根节点root ,和一个整数targetSum,求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。 示例1:输入:root=[10,5,-3,3,2,null,11,3,-2,null,1],target......
  • 2024-02-19-物联网C语言(9-链表)
    9.链表9.1概念假如:做一个班级信息管理系统,统计班级学生的信息而我们事先不知道班级人数,或者知道人数,但是中间人员可能发生变化:比如有新同学加入,有同学请假,又或者我们需要统计班级的平均成绩等等目标:要做一个类似QQ、飞秋类似的通信软件,其中有一个功能,类似用户上下线检测、......
  • Java实现静态链表
    本文参照了大话数据结构的静态链表的c语言实现packagecom.luoyi.list;/***@Description静态链表*@AuthorLuoyi*@Date2024/2/19**注:1.索引为0的节点不存放数据,cur指向第一个空闲节点的下标*2.最后一个元素(即下标Maxsize-1)的cur指向第一个有效数......
  • 「力扣」104. 二叉树的最大深度
    「力扣」104.二叉树的最大深度题目描述给定一个二叉树root,返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例1:输入:root=[3,9,20,null,null,15,7]输出:3示例2:输入:root=[1,null,2]输出:2提示:树中节点的数量在[0,10......