題目鏈接
難度： 中等 ??????類型：鏈表

給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

示例1

輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL

示例2

輸入: 0->1->2->NULL, k = 4
輸出: 2->0->1->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 2->0->1->NULL
向右旋轉(zhuǎn) 2 步: 1->2->0->NULL
向右旋轉(zhuǎn) 3 步: 0->1->2->NULL
向右旋轉(zhuǎn) 4 步: 2->0->1->NULL

解題思路

1.用快慢指針確定旋轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)
若鏈表的長度為n，讓快指針先走k%n步，然后快慢指針同時(shí)向前走，直到快指針的next為空，此時(shí)慢指針的next為旋轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)
2.移花接木
快指針的next指向原鏈表的頭節(jié)點(diǎn)head
head指向慢指針的next，作為新鏈表的頭節(jié)點(diǎn)返回
斷掉慢指針和head之間的鏈，否則會(huì)形成環(huán)

代碼實(shí)現(xiàn)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next:
            return head
        
        fast, slow = head, head
        # 找到fast的起始節(jié)點(diǎn)
        def findStart(fast, k):
            length = 0
            while k>0:
                k -= 1
                length += 1
                fast = fast.next
                if not fast:
                    fast = head                                    
                    k = k % length                    
                    return findStart(fast, k)
            return fast
                   
        fast = findStart(fast, k)
         
        while fast and fast.next:           
            fast = fast.next
            slow = slow.next
   
        fast.next = head
        head = slow.next
        slow.next = None
        return head