本篇推文共計2000個字，閱讀時間約3分鐘。

01

題目描述

題目描述：

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

示例1：

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

提示：

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

2.-100 <= Node.val <= 100

3.0 <= k <= 2 * 10^9

02

思路和方法

特殊情況的分析：我們在對鏈表進行操作時，應(yīng)該首先考慮到幾個問題。

1.鏈表長度不大于1時，此時鏈表長度為空或為1，不管怎么移動都還是原來的鏈表，此時直接輸出鏈表。

2.當(dāng)需要移動的次數(shù)k為0或者為鏈表長度n的倍數(shù)時，這時也是直接輸出鏈表就好。

將鏈表連接成環(huán)：首先要計算鏈表的長度n，并找到鏈表的末尾節(jié)點，將該節(jié)點與頭節(jié)點相連，這樣就得到了一個閉合為環(huán)的鏈表。

找到新斷開節(jié)點：閉合為環(huán)的鏈表后，我們需要根據(jù)鏈表移動的個數(shù)，找到我們需要斷開的那個節(jié)點。

即((n?1)?(k%n)),最終將得到的新鏈表輸出即可。

我們用代碼表示為:

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:

//對鏈表的特殊情況進行判斷
        if k == 0 or not head or not head.next:
            return head
        
        n = 1
        cur = head

//計算鏈表長度n
        while cur.next:
            cur = cur.next
            n += 1
  
//對鏈表移動的次數(shù)k是否為 鏈表長度n的倍數(shù) 進行判斷，
//同時確定新斷點的移動位置add
  
        if (add := n - k % n) == n:
            return head
        
//將鏈表鏈接成環(huán)
        cur.next = head

//尋找新鏈表的新斷點
        while add:
            cur = cur.next
            add -= 1
        
        ret = cur.next
        cur.next = None
        return ret