AC
題目描述：
給定一個鏈表仅讽，旋轉(zhuǎn)鏈表陶缺，將鏈表每個節(jié)點向右移動 k 個位置，其中 k 是非負數(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
算法過程：
思路一：繞圈法饱岸。
觀察示例可知，所謂翻轉(zhuǎn)這個鏈表徽千，無非就是把后幾個節(jié)點挪到前面罷了苫费。容易聯(lián)想到不過是形成1個圓，然后把新的頭返回即可
1）數(shù)節(jié)點個數(shù)
2）連接首尾節(jié)點
3）運動到新的頭部節(jié)點的上一位双抽，斷開鏈表
4）返回新的頭部節(jié)點
代碼：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
if head is None:
return None
#先數(shù)鏈表有幾個節(jié)點
i = head
count = 1
while i.next is not None:
i = i.next
count += 1
#拋掉重復的轉(zhuǎn)圈,也算一種算法優(yōu)化吧
k = k%count
if (k == 0) or count == 1:
return head
#把鏈表頭尾連起來
i.next = head
#從dummy開始運動
i = dummy
#運動到新的鏈表的頭的上一個節(jié)點
for _ in range(count - k):
i = i.next
j = i.next
i.next = None
return j
思路二：快慢指針
算法過程
1）定義2個指針百框，一快一慢
2）快的先走k步，慢的不動
3）接著快慢一起動牍汹，當快的走到節(jié)點的時候铐维，慢的的下一項就是新的頭部節(jié)點。
算法證明：
由過程可知慎菲，快的永遠比慢的快k步嫁蛇，所以當快的指針到尾部節(jié)點時，慢的指針距它還有k步遠露该。這時候我們從這里斷開鏈表睬棚，則能保證后k個節(jié)點移到前面來
代碼：
class Solution(object):
def rotateRight(self, head, k):
if not head or not head.next or k==0:
return head
ListLen = 0
p = head
#數(shù)有幾個節(jié)點
while(p):
ListLen+=1
p = p.next
#優(yōu)化
k = k%ListLen
if k==0:
return head
#快節(jié)點先走k步
p = head
while(k>0):
k -=1
p = p.next
slow = head
fast = p
#接著讓fast走到最后一個節(jié)點，slow與它有著同樣的速度
while fast.next:
slow = slow.next
fast = fast.next
#把頭尾連起來然后斷開鏈表
new_head = slow.next
fast.next = head
slow.next = None
return new_head
總結(jié)：快慢指針解幼，可以達到錯位運動的效果抑党，有時能制造很多trick魔法。
