当前位置：首页 > news >正文

leetcode刷题日记——旋转链表

news 2025/5/15 11:33:08

[ 题目描述 ]：
在这里插入图片描述
[ 思路 ]：

方法一，通过一个额外的数组去记录原链表的数据及其位置，然后通过数学算出旋转后各个值的位置去复制
其中 k 可能大于链表长度，所以要先将其对链表长度取余
运行如下

struct ListNode* rotateRight(struct ListNode* head, int k) {if (head == NULL || head->next == NULL || k == 0)return head;int sum=0;struct ListNode* temp=head;while(temp){temp=temp->next;sum++;}k=k%sum;temp=head;int* nums=(int*)malloc(sum*sizeof(int));for(int i=0;i<sum;i++){nums[i]=temp->val;temp=temp->next;}temp=head;for(int i=0;i<sum;i++){temp->val=nums[(i-k+sum)%sum];temp=temp->next;}return head;
}

方法二、循环链表，我们可以先将链表的尾部指向头部，形成一个循环链表
- 这样旋转链表，就是将倒数第 k 个节点作为头结点
运行如下

在这里插入图片描述

struct ListNode* rotateRight(struct ListNode* head, int k) {if (head == NULL || head->next == NULL || k == 0)return head;    struct ListNode* temp=head;int len=1,i=1;while(temp->next){temp=temp->next;len++;}temp->next=head;k%=len;while(i<len-k){head=head->next;i++;}temp=head;head=head->next;temp->next=NULL;return head;
}

[ 官方题解 ]：