给定一个链表，旋转链表，将链表的每个节点向右移动k个位置，其中k为非负数。给定一个链表，将链表向右旋转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解题思路：如果你看过上周的文章：LeetCode189：旋转数组，和这篇文章一样，旋转链表除了携带数据的结构不同。转为特定长度的数组：输入：1->2->3->4->5反转整个数组：5->4->3->2->1将链表前k位拆分为a段：5->4，3->2->1反转前??k位：4->5反转其余部分：1->2->3连接并输出：4->5->1->2->3按照这个思路是对链表进行3次反向链表，而反向链表在LeetCode206:Reversedlinkedlist一文中有详细介绍，使用迭代和递归两种方法，所以按照上面的方法解决这个问题也可以通过两种方式来完成。按照上面的思路，就类似于旋转数组的问题了，那我们再介绍另一种非常简单高效的方法。观察输入输出：输入：1->2->3->4->5，k=2输出：4->5->1->2->3切断节点3后的链表：1->2->3,4->5将头节点连接到尾节点：4->5->1->2->3输出：4->5->1->2->3感谢链表的特点，显然这种方法更简单，节点3的位置正好是len-k（len是链表的长度）。在第len-k个节点后切断并首尾相连。另外，k可能大于链表的长度，需要进行取余运算k=k%len。考虑到切节点的位置可能是最后一个节点，也可能是位置0（即头节点之前），显然没有必要切节点，但是如果上面的操作会导致指针溢出错误，可以先把第一个节点和最后一个节点连接起来，形成一个循环链表。Java:classSolution{publicListNoderotateRight(ListNodehead,intk){if(head==null||head.next==null||k==0)returnhead;intlen=1;ListNodecur=head;while(cur.next!=null){//计算链表长度cur=cur.next;长度++；}cur.next=head;intmod=len-k%len;//截断节点的位置cur=head;while(--mod>0)cur=cur.next;//找到切断节点ListNodenewHead=cur.next;//新链表头节点cur.next=null;//切断returnnewHead;}}Python3:类解决方案：defrotateRight(self,head:ListNode,k:int)->ListNode:ifnotheadornothead.nextornotk:returnheadcur=headlen=1whilecur.接下来：len+=1cur=cur。nextcur.next=headcur=headmod=len-k%lenwhilemod-1>0:cur=cur.nextmod-=1newHead=cur.nextcur.next=NonereturnnewHead欢迎关注微信。新工。一起学习的公众号：爱写bug
