关注下方公众号,分享满满的干货
描述
给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
思考
考虑以下几种情况:
特殊情况
一般情况
思路
以链表 1->2->3->4->5,k = 2 为栗,如下图示。
反思
采用 双指针 中的 快慢指针 。
本题设置 虚拟头节点 的作用是找到 新链表的头节点和尾节点。通过 快慢指针 去寻找。
ListNode* rotateRight(ListNode* head, int k) {
/* 特殊情况判断 */
if (head == nullptr || head->next == nullptr || k == 0) {
return head;
}
/* 增加虚拟头节点 */
ListNode* dummy = new ListNode(0);
dummy->next = head;
/* 获取链表长度 */
int len = 0;
for (ListNode* node = head; node != nullptr; node = node->next) {
len++;
}
k %= len;
/* 判断 k 是否是 len 的整数倍 */
if (k == 0) {
return head;
}
/* 获取新链表的头尾节点 */
ListNode *fast = dummy, *slow = dummy;
for (int i = 0; i < k; ++i) {
fast = fast->next;
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
fast->next = head;
head = slow->next;
slow->next = nullptr;
/* 释放虚拟头节点 */
delete dummy;
return head;
}
ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
int len = 0;
for (ListNode node = head; node != null; node = node.next) {
len++;
}
k %= len;
if (k == 0) {
return head;
}
ListNode fast = dummy, slow = dummy;
for (int i = 0; i < k; ++i) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
fast.next = head;
head = slow.next;
slow.next = null;
return head;
}