一、題目描述

給你一個鏈表的頭節(jié)點head，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點向右移動k個位置。

示例 1：

輸入：head =[1,2,3,4,5], k = 2
輸出：[4,5,1,2,3]

示例 2：

輸入：head =[0,1,2], k = 4
輸出：[2,0,1]

提示：

鏈表中節(jié)點的數(shù)目在范圍 [0, 500] 內(nèi)

-100 <= Node.val <= 100

0 <= k <= 2 * 10^9

原題地址：https://leetcode.cn/problems/rotate-list/

二、題目解析

1、首先遍歷整個鏈表，求出鏈表的長度len。

2、根據(jù)題目的提示，k可能很大，遠(yuǎn)超鏈表的長度，這樣就會導(dǎo)致一種情況，比如 k = 1000，len = 999，每個節(jié)點向右移動 1 個節(jié)點和向右移動 k = 1000 個節(jié)點結(jié)果一樣，所以進行一個取模的操作可以節(jié)省大量的移動操作。

3、接下來設(shè)置兩個指針 former、latter 均指向鏈表的頭節(jié)點，這兩個指針的目的是去尋找出旋轉(zhuǎn)之前的尾節(jié)點位置、旋轉(zhuǎn)成功之后的尾節(jié)點位置。

4、先讓former指針先向前移動 k 次，此時，former就和latter相距 k 個節(jié)點了。

5、接下來，讓former、latter同時向后移動，直到former來到了最后一個節(jié)點位置。

6、這個時候，從head到latter有len - k個節(jié)點，latter + 1 到 former 有 k 個節(jié)點。

7、也就意味著，latter + 1這個節(jié)點是移動 k 個節(jié)點成功之后的頭節(jié)點。

8、只需要返回latter + 1后面這個節(jié)點newHead，并且斷開連接就行了。

三、參考代碼

1、Java 代碼

//登錄AlgoMooc官網(wǎng)獲取更多算法圖解
//https://www.algomooc.com
//作者：程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢吳師兄呀
//旋轉(zhuǎn)鏈表（LeetCode61）//leetcode.cn/problems/rotate-list/
classSolution{
publicListNoderotateRight(ListNodehead,intk){

//邊界條件判斷
if(head==null){
returnhead;
}

//1、第一步先要計算出鏈表的長度來
intlen=0;

//2、這里我們設(shè)置一個指針指向鏈表的頭節(jié)點的位置
ListNodetempHead=head;

//3、通過不斷的移動tempHead，來獲取鏈表的長度
while(tempHead!=null){

//tempHead不斷向后移動，直到為null
tempHead=tempHead.next;

//每次遍歷一個新的節(jié)點，意味著鏈表長度新增1
len++;

}

//由于題目中的k會超過鏈表的長度，因此進行一個取余的操作
//比如k=1000，len=999
//實際上就是將鏈表每個節(jié)點向右移動1000%999=1個位置就行了
//因為鏈表中的每個節(jié)點移動len次會回到原位
k=k%len;


//4、接下來設(shè)置兩個指針指向鏈表的頭節(jié)點
//這兩個指針的目的是去尋找出旋轉(zhuǎn)之前的尾節(jié)點位置、旋轉(zhuǎn)成功之后的尾節(jié)點位置

//former指針
ListNodeformer=head;

//latter指針
ListNodelatter=head;

//former指針先向前移動k次
for(inti=0;i

	

	2、C++ 代碼

	
classSolution{
public:
ListNode*rotateRight(ListNode*head,intk){

//邊界條件判斷
if(head==NULL){
returnhead;
}

//1、第一步先要計算出鏈表的長度來
intlen=0;

//2、這里我們設(shè)置一個指針指向鏈表的頭節(jié)點的位置
ListNode*tempHead=head;

//3、通過不斷的移動tempHead，來獲取鏈表的長度
while(tempHead!=NULL){

//tempHead不斷向后移動，直到為NULL
tempHead=tempHead->next;

//每次遍歷一個新的節(jié)點，意味著鏈表長度新增1
len++;

}

//由于題目中的k會超過鏈表的長度，因此進行一個取余的操作
//比如k=1000，len=999
//實際上就是將鏈表每個節(jié)點向右移動1000%999=1個位置就行了
//因為鏈表中的每個節(jié)點移動len次會回到原位
k=k%len;


//4、接下來設(shè)置兩個指針指向鏈表的頭節(jié)點
//這兩個指針的目的是去尋找出旋轉(zhuǎn)之前的尾節(jié)點位置、旋轉(zhuǎn)成功之后的尾節(jié)點位置

//former指針
ListNode*former=head;

//latter指針
ListNode*latter=head;

//former指針先向前移動k次
for(inti=0;inext;

}

//這樣former和latter就相差了k個節(jié)點
//5、接下來，兩個指針同時向后移動，直到former來到了最后一個節(jié)點位置
while(former->next!=NULL){

//former不斷向后移動
former=former->next;

//latter不斷向后移動
latter=latter->next;
}

//6、此時，former指向了最后一個節(jié)點，需要將這個節(jié)點和原鏈表的頭節(jié)點連接起來
former->next=head;

//7、latter指向的節(jié)點的【下一個節(jié)點】是倒數(shù)第k個節(jié)點，那就是旋轉(zhuǎn)成功之后的頭節(jié)點
ListNode*newHead=latter->next;

//8、斷開鏈接，避免成環(huán)
latter->next=NULL;

//9、返回newHead
returnnewHead;

}
};


	

	3、Python 代碼

	
classSolution:
defrotateRight(self,head:Optional[ListNode],k:int)->Optional[ListNode]:
#邊界條件判斷
ifnotheadork==0:
returnhead

#1、第一步先要計算出鏈表的長度來
_len=0

#2、這里我們設(shè)置一個指針指向鏈表的頭節(jié)點的位置
tempHead=head

#3、通過不斷的移動tempHead，來獲取鏈表的長度
whiletempHead:

#tempHead不斷向后移動，直到為NULL
tempHead=tempHead.next

#每次遍歷一個新的節(jié)點，意味著鏈表長度新增1
_len+=1



#由于題目中的k會超過鏈表的長度，因此進行一個取余的操作
#比如k=1000，len=999
#實際上就是將鏈表每個節(jié)點向右移動1000%999=1個位置就行了
#因為鏈表中的每個節(jié)點移動len次會回到原位
k=k%_len


#4、接下來設(shè)置兩個指針指向鏈表的頭節(jié)點
#這兩個指針的目的是去尋找出旋轉(zhuǎn)之前的尾節(jié)點位置、旋轉(zhuǎn)成功之后的尾節(jié)點位置

#former指針
former=head

#latter指針
latter=head

#former指針先向前移動k次
foriinrange(0,k):

#former不斷向后移動
former=former.next


#這樣former和latter就相差了k個節(jié)點
#5、接下來，兩個指針同時向后移動，直到former來到了最后一個節(jié)點位置
whileformer.next:

#former不斷向后移動
former=former.next

#latter不斷向后移動
latter=latter.next


#6、此時，former指向了最后一個節(jié)點，需要將這個節(jié)點和原鏈表的頭節(jié)點連接起來
former.next=head

#7、latter指向的節(jié)點的【下一個節(jié)點】是倒數(shù)第k個節(jié)點，那就是旋轉(zhuǎn)成功之后的頭節(jié)點
newHead=latter.next

#8、斷開鏈接，避免成環(huán)
latter.next=None

#9、返回newHead
returnnewHead


	

	四、復(fù)雜度分析

	時間復(fù)雜度：鏈表一共被遍歷兩次，因此總的時間復(fù)雜度為O(n)，n是鏈表的長度。

	空間復(fù)雜度：O(1)，我們只需要常數(shù)的空間存儲若干變量。

	




	審核編輯：劉清