LeetCode刷题（178）～旋转链表【细节】

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

解答 By 海轰

提交代码

ListNode* rotateRight(ListNode* head, int k) { if(k==0|| !head || !head->next) return head; int lengths=0; ListNode* h=head; while(h){ ++lengths; h=h->next; } int newk=k%lengths; if(newk==0) return head; newk=lengths-newk; h=head; while(newk--){ h=h->next; } ListNode* ans=h; while(h->next){ h=h->next; } h->next=head; while(h->next!=ans){ h=h->next; } h->next=NULL; return ans; }

运行结果 提交代码【优化版】

ListNode* rotateRight(ListNode* head, int k) { if(k==0|| !head || !head->next) return head; int lengths=1; ListNode* h=head; while(h->next){ ++lengths; h=h->next; }// 此时h就是指向最后一个元素 int newk=k%lengths; if(newk==0) return head; newk=lengths-newk-1; ListNode* temp=head; while(newk--){ temp=temp->next; } ListNode* ans=temp->next; temp->next=NULL; h->next=head; return ans; }

运行结果

题目来源

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotate-list

海轰Pro 认证博客专家 C/C 微信小程序 微信小程序：「海轰Pro」微信公众号：「海轰Pro」知乎：「海轰Pro」微博：「海轰Pro」