?目錄

一、題目描述

二、整體思路

三、代碼

---

一、題目描述

?

原題鏈接

二、整體思路

? ? ? ? 首先發(fā)現(xiàn)這樣的規(guī)律：當(dāng)k大于等于鏈表中節(jié)點(diǎn)總數(shù)n時(shí)，會發(fā)現(xiàn)此時(shí)旋轉(zhuǎn)后的鏈表和k=k%n時(shí)的旋轉(zhuǎn)后的鏈表一樣。同時(shí)對于特殊情況n=0和n=1時(shí)，無論k的值為多少都可以直接返回head。

? ? ? ? 因?yàn)閗的所有取值情況都可以通過規(guī)律化歸解決，同時(shí)旋轉(zhuǎn)后的鏈表元素依然為原來鏈表中的元素且后續(xù)節(jié)點(diǎn)順序與原鏈表相同。因此我們可以在鏈表尾部再接上一個(gè)和原來鏈表一模一樣的鏈表，找到旋轉(zhuǎn)k次之后的頭結(jié)點(diǎn)，再從此截取原鏈表長度的結(jié)點(diǎn)作為返回值。

? ? ? ? n-k的由來：旋轉(zhuǎn)k次，代表從鏈表尾部往前數(shù)第k個(gè)結(jié)點(diǎn)為新的頭結(jié)點(diǎn)，那么從鏈表頭往后數(shù)就是第n-k個(gè)結(jié)點(diǎn)。

三、代碼
?

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head==null || head.next==null) return head;int n=1;ListNode nxt=head;ListNode last=head;while(last.next!=null){last=last.next;n++;}if(k%n==0) return head;last.next=nxt;for(int i=0;i<n-(k%n);i++){head=head.next;}ListNode ret=head;for(int j=1;j<n;j++){ret=ret.next;}ret.next=null;return head;}
}