【LeetCode每日一题】61. 旋转链表
【LeetCode每日一题】61. 旋转链表
公众号guangcity
发布于 2021-03-30 14:42:44
发布于 2021-03-30 14:42:44
【LeetCode每日一题】61. 旋转链表
本题有两种做法，方法都是找到关键点进行连接，两个关键点需要找到：
- 新头节点在原链表中的位置 - 1(前一个结点)
- 最后一个有效结点(node->next == NULL)
随后将这两个点进行连接。
解法1：计算总和记录最后一个结点，下次遍历记录新链表头结点的前一个结点。
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next) return head;
ListNode* p = head;
int node_sum = 1;
while (p->next) {
node_sum++;
p = p->next;
}
ListNode* tail = p;
int x = k % node_sum;
if (!x) return head;
int i = 1;
p = head;
while (i<node_sum-x) {
p = p->next;
i++;
}
ListNode* newHead = p->next;
tail->next = head;
p->next = nullptr;
return newHead;
}
};
解法2：使用快慢指针，让fast先抵达k+1结点，随后一起遍历，当fast抵达最后一个结点，slow此时便是要寻找的新链表头节点的前一个结点。
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next) return head;
ListNode* p = head;
int node_sum = 0;
while (p) {
node_sum++;
p = p->next;
}
int x = k % node_sum;
if (!x) return head;
ListNode* slow = head, *fast = head;
while (x--) {
fast = fast->next;
}
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
ListNode* newHead = slow->next;
fast->next = head;
slow->next = nullptr;
return newHead;
}
};
本节完
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-03-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录