題目鏈接
難度： 中等 ??????類(lèi)型：鏈表
給定一個(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)
若鏈表的長(zhǎng)度為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
