61. 旋转链表 - 力扣（LeetCode）
61. 旋转链表 - 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 示例 1： [https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg] 输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3] 示例 2： [https://assets.leetcode.com/uploads/2020/11/13/roate2.jpg] 输入：head =...
还在旋转，还在旋转 
思路
实际的移动次数是 k 对链表长度取模。取模后取链表后 k 个节点，接到开头即可。
注意链表可能为空。
代码
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr) {
return head;
}
// 先求出整个链表的长度
int n = 0;
ListNode *ptr = head, *tail = nullptr;
while (ptr != nullptr) {
n++;
if (ptr->next == nullptr) {
tail = ptr;
}
ptr = ptr->next;
}
// 计算实际移动次数
k %= n;
// 找到后 k 个结点接到开头即可
if (k == 0) {
return head;
}
ptr = head;
ListNode* prev = nullptr;
// 移动指针到后 k 个节点的开头
for (int i = 0; i < n - k; i++) {
prev = ptr;
ptr = ptr->next;
}
// 前后两截断开
if (prev != nullptr) {
prev->next = nullptr;
}
// 把前一截接到后一截后面
tail->next = head;
return ptr;
}
};
1 个帖子 - 1 位参与者
来源: linux.do查看原文