移動(dòng)旋轉(zhuǎn)鏈表的每個(gè)節(jié)點(diǎn)

一、題目描述

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

示例 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é)點(diǎn)的數(shù)目在范圍 [0, 500] 內(nèi)

-100 <= Node.val <= 100

0 <= k <= 2 * 10^9

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

二、題目解析

1、首先遍歷整個(gè)鏈表，求出鏈表的長(zhǎng)度len。

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

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

4、先讓former指針先向前移動(dòng) k 次，此時(shí)，former就和latter相距 k 個(gè)節(jié)點(diǎn)了。

5、接下來(lái)，讓former、latter同時(shí)向后移動(dòng)，直到former來(lái)到了最后一個(gè)節(jié)點(diǎn)位置。

6、這個(gè)時(shí)候，從head到latter有len - k個(gè)節(jié)點(diǎn)，latter + 1 到 former 有 k 個(gè)節(jié)點(diǎn)。

7、也就意味著，latter + 1這個(gè)節(jié)點(diǎn)是移動(dòng) k 個(gè)節(jié)點(diǎn)成功之后的頭節(jié)點(diǎn)。

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

三、參考代碼

1、Java 代碼

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

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

//1、第一步先要計(jì)算出鏈表的長(zhǎng)度來(lái)
intlen=0;

//2、這里我們?cè)O(shè)置一個(gè)指針指向鏈表的頭節(jié)點(diǎn)的位置
ListNodetempHead=head;

//3、通過(guò)不斷的移動(dòng)tempHead，來(lái)獲取鏈表的長(zhǎng)度
while(tempHead!=null){

//tempHead不斷向后移動(dòng)，直到為null
tempHead=tempHead.next;

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

}

//由于題目中的k會(huì)超過(guò)鏈表的長(zhǎng)度，因此進(jìn)行一個(gè)取余的操作
//比如k=1000，len=999
//實(shí)際上就是將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)1000%999=1個(gè)位置就行了
//因?yàn)殒湵碇械拿總€(gè)節(jié)點(diǎn)移動(dòng)len次會(huì)回到原位
k=k%len;


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

//former指針
ListNodeformer=head;

//latter指針
ListNodelatter=head;

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

	

	2、C++ 代碼

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

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

//1、第一步先要計(jì)算出鏈表的長(zhǎng)度來(lái)
intlen=0;

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

//3、通過(guò)不斷的移動(dòng)tempHead，來(lái)獲取鏈表的長(zhǎng)度
while(tempHead!=NULL){

//tempHead不斷向后移動(dòng)，直到為NULL
tempHead=tempHead->next;

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

}

//由于題目中的k會(huì)超過(guò)鏈表的長(zhǎng)度，因此進(jìn)行一個(gè)取余的操作
//比如k=1000，len=999
//實(shí)際上就是將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)1000%999=1個(gè)位置就行了
//因?yàn)殒湵碇械拿總€(gè)節(jié)點(diǎn)移動(dòng)len次會(huì)回到原位
k=k%len;


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

//former指針
ListNode*former=head;

//latter指針
ListNode*latter=head;

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

}

//這樣former和latter就相差了k個(gè)節(jié)點(diǎn)
//5、接下來(lái)，兩個(gè)指針同時(shí)向后移動(dòng)，直到former來(lái)到了最后一個(gè)節(jié)點(diǎn)位置
while(former->next!=NULL){

//former不斷向后移動(dòng)
former=former->next;

//latter不斷向后移動(dòng)
latter=latter->next;
}

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

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

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

//9、返回newHead
returnnewHead;

}
};


	

	3、Python 代碼

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

#1、第一步先要計(jì)算出鏈表的長(zhǎng)度來(lái)
_len=0

#2、這里我們?cè)O(shè)置一個(gè)指針指向鏈表的頭節(jié)點(diǎn)的位置
tempHead=head

#3、通過(guò)不斷的移動(dòng)tempHead，來(lái)獲取鏈表的長(zhǎng)度
whiletempHead:

#tempHead不斷向后移動(dòng)，直到為NULL
tempHead=tempHead.next

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



#由于題目中的k會(huì)超過(guò)鏈表的長(zhǎng)度，因此進(jìn)行一個(gè)取余的操作
#比如k=1000，len=999
#實(shí)際上就是將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)1000%999=1個(gè)位置就行了
#因?yàn)殒湵碇械拿總€(gè)節(jié)點(diǎn)移動(dòng)len次會(huì)回到原位
k=k%_len


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

#former指針
former=head

#latter指針
latter=head

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

#former不斷向后移動(dòng)
former=former.next


#這樣former和latter就相差了k個(gè)節(jié)點(diǎn)
#5、接下來(lái)，兩個(gè)指針同時(shí)向后移動(dòng)，直到former來(lái)到了最后一個(gè)節(jié)點(diǎn)位置
whileformer.next:

#former不斷向后移動(dòng)
former=former.next

#latter不斷向后移動(dòng)
latter=latter.next


#6、此時(shí)，former指向了最后一個(gè)節(jié)點(diǎn)，需要將這個(gè)節(jié)點(diǎn)和原鏈表的頭節(jié)點(diǎn)連接起來(lái)
former.next=head

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

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

#9、返回newHead
returnnewHead


	

	四、復(fù)雜度分析

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

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

	




	審核編輯：劉清