1. 题目描述
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
2. 初解
和24题一样同样是考察链表的基本变换,不熟悉的情况下还是先画图理清思路:
首先找到链表的末尾的两个元素
这就是右移一次的过程,右移k次做k次循环即可。
你以为这就完了?奶衣乌。测试用例里居然出现了k=100000000000这种测试用例,好吧,算你狠,还是求一下模算一下最少需要右移几步把。。。
3. 代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* rotateRight(struct ListNode* head, int k) {
int count = 2;
if (head == NULL || head->next == NULL) { // 如果是空链表或者只有一个节点
return head;
}
struct ListNode* prev = head;
struct ListNode* curr = head->next;
while (curr->next != NULL) { // 找到最后两个元素
curr = curr->next;
prev = prev->next;
count++;
}
k = k % count;
for (int i = 0; i < k; i++) {
prev->next = curr->next;
curr->next = head;
head = curr;
while (curr->next != prev) {
curr = curr->next;
}
prev = curr;
curr = curr->next;
}
return head;
}
struct ListNode* CreatLL(int* arr, int size) {
struct ListNode* dummyHead =
(struct ListNode *)malloc(sizeof(struct ListNode));
dummyHead->val = 0;
dummyHead->next = NULL;
struct ListNode* ptr = dummyHead;
struct ListNode* tmp;
for (int i = 0; i < size; i++) {
tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
tmp->next = NULL;
tmp->val = arr[i];
ptr->next = tmp;
ptr = ptr->next;
}
return dummyHead->next;
}
void printLL(struct ListNode* head) {
struct ListNode* ptr = head;
while (ptr) {
printf("%d -> ", ptr->val);
ptr = ptr->next;
}
putchar('\n');
}
int main() {
int arr[] = { 0, 1, 2 };
struct ListNode* head = CreatLL(arr, 3);
printLL(head);
head = rotateRight(head, 4);
printLL(head);
system("pause");
return 0;
}
4. 改进
又到了LeetCode上的大佬使用降维打击的时候了。
我的原方法必须一次一次旋转,总共旋转k次,那有没有什么办法一次就旋转到位呢?答案当然是肯定的,只是需要变换一下思路。链表这种数据结构与字符串还有数组不同,把链表首尾相连成环,此时移动head的指向不就相当于旋转链表嘛!最后只要在对应的位置把环断开就得到了旋转后的链表
struct ListNode* rotateRight1(struct ListNode* head, int k) {
if (head == NULL || head->next == NULL)
return head;
struct ListNode* tail = head;
struct ListNode* newHead = head;
int length = 1;
// 先找到链表尾节点
while (tail->next) {
tail = tail->next;
length++;
}
k %= length;
// 链表成环
tail->next = head;
// 右移k次,相当于左移length - k次
for (int i = 0; i < length - k; i++) {
newHead = newHead->next;
tail = tail->next;
}
tail->next = NULL;
return newHead;
}