iis服务器助手广告广告
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++实现旋转链表
  • 474
分享到

C++实现旋转链表

2023-06-20 16:06:28 474人浏览 泡泡鱼
摘要

这篇文章主要介绍“c++实现旋转链表”,在日常操作中,相信很多人在C++实现旋转链表问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++实现旋转链表”的疑惑有所帮助!接下来,请跟着小编一起来学习吧![Leet

这篇文章主要介绍“c++实现旋转链表”,在日常操作中,相信很多人在C++实现旋转链表问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++实现旋转链表”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

[LeetCode] 61. Rotate List 旋转链表

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

C++实现旋转链表

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

C++实现旋转链表

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

  • The number of nodes in the list is in the range [0, 500].

  • -100 <= Node.val <= 100

  • 0 <= k <= 2 * 109

这道旋转链表的题和之前那道 Rotate Array 很类似,但是比那道要难一些,因为链表的值不能通过下表来访问,只能一个一个的走,博主刚开始拿到这题首先想到的就是用快慢指针来解,快指针先走k步,然后两个指针一起走,当快指针走到末尾时,慢指针的下一个位置是新的顺序的头结点,这样就可以旋转链表了,自信满满的写完程序,放到 OJ 上跑,以为能一次通过,结果跪在了各种特殊情况,首先一个就是当原链表为空时,直接返回NULL,还有就是当k大于链表长度和k远远大于链表长度时该如何处理,需要首先遍历一遍原链表得到链表长度n,然后k对n取余,这样k肯定小于n,就可以用上面的算法了,代码如下:

 解法一:

class Solution {public:    ListNode *rotateRight(ListNode *head, int k) {        if (!head) return NULL;        int n = 0;        ListNode *cur = head;        while (cur) {            ++n;            cur = cur->next;        }        k %= n;        ListNode *fast = head, *slow = head;        for (int i = 0; i < k; ++i) {            if (fast) fast = fast->next;        }        if (!fast) return head;        while (fast->next) {            fast = fast->next;            slow = slow->next;        }        fast->next = head;        fast = slow->next;        slow->next = NULL;        return fast;    }};

这道题还有一种解法,跟上面的方法类似,但是不用快慢指针,一个指针就够了,原理是先遍历整个链表获得链表长度n,然后此时把链表头和尾链接起来,在往后走 n - k%n 个节点就到达新链表的头结点前一个点,这时断开链表即可,代码如下:

class Solution {public:    ListNode *rotateRight(ListNode *head, int k) {        if (!head) return NULL;        int n = 1;        ListNode *cur = head;        while (cur->next) {            ++n;            cur = cur->next;        }        cur->next = head;        int m = n - k % n;        for (int i = 0; i < m; ++i) {            cur = cur->next;        }        ListNode *newhead = cur->next;        cur->next = NULL;        return newhead;    }};

到此,关于“C++实现旋转链表”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注编程网网站,小编会继续努力为大家带来更多实用的文章!

--结束END--

本文标题: C++实现旋转链表

本文链接: https://www.lsjlt.com/news/298207.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • c语言怎么计算字符串长度
    在C语言中,可以使用内置的strlen()函数来计算字符串的长度。该函数位于string.h头文件中。以下是一个示例代码: #inc...
    99+
    2024-05-14
    c语言
  • c语言怎么判断三个数的大小
    可以通过比较三个数之间的大小关系来判断它们的大小。以下是一个示例代码: #include <stdio.h> int ...
    99+
    2024-05-14
    c语言
  • c++排序函数sort怎么使用
    在C++中,使用sort函数对容器中的元素进行排序,可以按照默认的升序排列,也可以自定义排序规则。 下面是一个简单的例子,对一个ve...
    99+
    2024-05-14
    c++
  • c++中string的compare函数怎么使用
    在C++中,可以使用string的compare函数来比较两个string对象的大小。该函数的原型如下: int compare(c...
    99+
    2024-05-14
    c++
  • c++中string的compare函数有什么用
    c++中string的compare函数用于比较两个字符串的大小关系。该函数返回一个整数值,表示两个字符串的比较结果。 具体来说,如...
    99+
    2024-05-14
    c++
  • c++中print函数的功能有哪些
    在C++中,通常使用std::cout来进行输出操作,而不是使用print函数。std::cout是C++标准库中的一个输出流对象,...
    99+
    2024-05-14
    c++
  • c语言数据结构怎么使用
    在C语言中,数据结构可以通过定义结构体来实现。以下是一些常见的数据结构的使用方法示例: 链表: #include <std...
    99+
    2024-05-14
    c语言
  • c++中print函数的用法是什么
    在C++中没有内置的print函数,但可以使用cout来输出内容到控制台。cout是C++标准库中的一个输出流对象,可以使用<...
    99+
    2024-05-14
    c++
  • c++中concept的用法是什么
    在C++20中,Concept是一种新的语言特性,用于定义类型要求和约束。Concept可以被用来约束函数模板、类模板和普通函数的参...
    99+
    2024-05-14
    c++
  • c++中concept的作用是什么
    在C++中,concept的作用是定义一种通用的约束,用于限制模板参数的类型范围。通过使用concept,可以在编译时对模板参数进行...
    99+
    2024-05-14
    c++
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作