LeetCode 61. 旋转链表
2023-09-14 09:13:12 时间
难度: m i d d l e \color{orange}{middle} middle
题目描述
给你一个链表的头节点 h e a d head head ,旋转链表,将链表每个节点向右移动 k k 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 ] [0, 500] [0,500] 内
- − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100
- 0 < = k < = 2 ∗ 1 0 9 0 <= k <= 2 * 10^{9} 0<=k<=2∗109
算法
(模拟,连接) O ( n ) O(n) O(n)
- 这道题中 k 可能很大,所以我们令 k=k%n,n是链表长度。
- 创建两个指针 first, second,分别指向头结点,先让 first 向后移动 k个位置,然后first和second同时向后移动,直到first走到链表最后一个元素。
- 此时first指向链表末尾,second指向分界点。然后我们把链表从分界点处断开,然后把后半段接在前半段前面即可。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head) return head;
int n = 0;
ListNode* p = head;
while (p) {
n ++;
p = p->next;
}
k %= n;
if (k == 0) return head;
ListNode* first = head;
while(k -- && first != NULL) first = first->next;
ListNode* second = head;
while (first->next) {
first = first->next;
second = second->next;
}
first->next = head;
head = second->next;
second->next = 0;
return head;
}
};
相关文章
- Java实现 LeetCode 691 贴纸拼词(DFS+map记录)
- Java实现 LeetCode 492 构造矩形
- Java实现 LeetCode 417 太平洋大西洋水流问题
- Java实现 LeetCode 416 分割等和子集
- Java实现 LeetCode 382 链表随机节点
- Java实现 LeetCode 328 奇偶链表
- Java实现 LeetCode 315 计算右侧小于当前元素的个数
- Java实现 LeetCode 237 删除链表中的节点
- Java实现 LeetCode 234 回文链表
- Java实现 LeetCode 160 相交链表
- Java实现 LeetCode 143 重排链表
- Java实现 LeetCode 83 删除排序链表中的重复元素
- Java实现 LeetCode 61 旋转链表
- LeetCode(21):合并两个有序链表
- LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium
- LeetCode(61):旋转链表
- (链表专题) 725. 分隔链表 ——【Leetcode每日一题】
- (链表专题) 328. 奇偶链表 ——【Leetcode每日一题】
- leetcode 面试题 08.12. 八皇后----回溯篇7
- LeetCode 283 Move Zeroes(移动全部的零元素)
- 【LeetCode Python实现】二次元日麻游戏 雀魂麻将
- Leetcode 645. 错误的集合
- [LeetCode] 19. 删除链表的倒数第N个节点 ☆☆☆
- [LeetCode] 72. 编辑距离 ☆☆☆☆☆(动态规划)
- leetcode 1019. 链表中的下一个更大节点 js实现
- leetcode 788. Rotated Digits
- 【Leetcode刷题Python】206.反转链表
- 【Leetcode刷题Python】从列表list中创建一颗二叉树
- 【Leetcode刷题Python】剑指 Offer 26. 树的子结构