今天是紀錄LeetCode解題的第六十一天
堅持兩個月了!

第六十一題題目：

給定一個鏈結串列head，將鏈結串列向右旋轉k位

解題思路

我們先計算整個鏈結串列的長度n，再用n % k算出要旋轉的次數(k可能很大，實際上如果n = 5，k = 7時不用旋轉7次，而是只需要旋轉2次即可)，接著我們進行旋轉，首先要有cur指向最後一個節點和prev指向倒數第二個節點，然後把prev指向None，cur指回原本的head，然後讓head等於cur(以範例1來說，cur指向節點5，prev指向節點4，而旋轉完節點4應該指向None也就是變成整個鏈結串列的尾巴，所以這裡我們將prev指向None，而cur指回原本的head，也就是指向節點1的部分，最後我們要把head等於cur，因為head原本指向1 → 2 → 3...，讓它等於cur，head會變成5 → 1 → 2 → 3 → 4)

程式碼

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0:
            return head
        n = 1 #先算鏈結串列長度
        tail = head
        while tail.next:
            tail = tail.next
            n += 1
        k = k % n #計算要旋轉幾次，假設鏈結串列長度為5，旋轉k次(k=5)，那麼k % n就等於沒旋轉，我們只需要旋轉k % n次而已
        if k == 0:
            return head
        for _ in range(k):
            prev = None
            cur = head
            #找到最後一個節點與倒數第二個節點
            while cur.next:
                prev = cur
                cur = cur.next
            #把尾巴接到頭，然後切斷原本的尾巴
            prev.next = None
            cur.next = head
            head = cur
        return head

執行過程(head = [1,2,3,4,5]，k = 2)