LeetCode(61):旋转链表
2023-09-14 08:59:35 时间
Medium!
题目描述:
给定一个链表,旋转链表,将链表每个节点向右移动 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
解题思路:
这道旋转链表的题和之前那道 Rotate Array 旋转数组 很类似,但是比那道要难一些,因为链表的值不能通过下标来访问,只能一个一个的走,我们可能首先想到的就是用快慢指针来解,快指针先走k步,然后两个指针一起走,当快指针走到末尾时,慢指针的下一个位置是新的顺序的头结点,这样就可以旋转链表了,自信满满地写完程序,放到OJ上跑,以为能一次通过,结果就跪在了各种特殊情况,首先一个就是当原链表为空时,直接返回NULL,还有就是当k大于链表长度和k远远大于链表长度时该如何处理,我们需要首先遍历一遍原链表得到链表长度n,然后k对n取余,这样k肯定小于n,就可以用上面的算法了。
C++解法一:
1 class Solution { 2 public: 3 ListNode *rotateRight(ListNode *head, int k) { 4 if (!head) return NULL; 5 int n = 0; 6 ListNode *cur = head; 7 while (cur) { 8 ++n; 9 cur = cur->next; 10 } 11 k %= n; 12 ListNode *fast = head, *slow = head; 13 for (int i = 0; i < k; ++i) { 14 if (fast) fast = fast->next; 15 } 16 if (!fast) return head; 17 while (fast->next) { 18 fast = fast->next; 19 slow = slow->next; 20 } 21 fast->next = head; 22 fast = slow->next; 23 slow->next = NULL; 24 return fast; 25 } 26 };
这道题还有一种解法,跟上面的方法类似,但是不用快慢指针,一个指针就够了,原理是先遍历整个链表获得链表长度n,然后此时把链表头和尾链接起来,再往后走n - k % n个节点就到达新链表的头结点前一个点,这时断开链表即可。
C++解法二:
1 class Solution { 2 public: 3 ListNode *rotateRight(ListNode *head, int k) { 4 if (!head) return NULL; 5 int n = 1; 6 ListNode *cur = head; 7 while (cur->next) { 8 ++n; 9 cur = cur->next; 10 } 11 cur->next = head; 12 int m = n - k % n; 13 for (int i = 0; i < m; ++i) { 14 cur = cur->next; 15 } 16 ListNode *newhead = cur->next; 17 cur->next = NULL; 18 return newhead; 19 } 20 };
相关文章
- Leetcode 之Length of Last Word(37)
- Java实现 LeetCode 795 区间子数组个数 (暴力分析)
- Java实现 LeetCode 784 字母大小写全排列(DFS)
- Java实现 LeetCode 725 分隔链表(暴力)
- Java实现 LeetCode 508 出现次数最多的子树元素和
- Java实现 LeetCode 275 H指数 II
- Java实现 LeetCode 237 删除链表中的节点
- Java实现 LeetCode 148 排序链表
- Java实现 LeetCode 147 对链表进行插入排序
- Java实现 LeetCode 143 重排链表
- Java实现 LeetCode 109 有序链表转换二叉搜索树
- Java实现 LeetCode 61 旋转链表
- Java实现 LeetCode 25 K个一组翻转链表
- 【贪心】LeetCode 714. 买卖股票的最佳时机含手续费【中等】
- LeetCode(61):旋转链表
- LeetCode(15): 每k个一组翻转链表
- LeetCode(7):颠倒整数
- LeetCode-121. 买卖股票的最佳时机【单调栈,一次遍历】==注意暴力解法会超时。==
- LeetCode-1200. 最小绝对差【数组,排序】
- LeetCode-905. 按奇偶排序数组【数组,双指针,排序】
- LeetCode-21. 合并两个有序链表
- 【LeetCode 12】整数转罗马数字
- leetCode 82.Remove Duplicates from Sorted List II (删除排序链表的反复II) 解题思路和方法
- Leetcode 1351. 统计有序矩阵中的负数
- 【Leetcode刷题Python】138. 复制带随机指针的链表
- 【Leetcode刷题Python】70. 爬楼梯
- 【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
- LeetCode 237. 删除链表中的节点
- LeetCode 24. 两两交换链表中的节点