一步一個腳印的python leetcode 題解。本人一直在努力地積累Leetcode上用Python實現的題，並且會盡力講清每道題的原理，絕不像其他某些部落格簡略地帶過。
如果覺得講的清楚，歡迎關注。
題目描述：
給定一個連結串列，旋轉連結串列，將連結串列每個節點向右移動 k 個位置，其中 k 是非負數。
示例 1:
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉 1 步: 5->1->2->3->4->NULL
向右旋轉 2 步: 4->5->1->2->3->NULL
示例 2:
輸入: 0->1->2->NULL, k = 4 輸出:2->0->1->NULL解釋: 向右旋轉 1 步: 2->0->1->NULL 向右旋轉 2 步: 1->2->0->NULL 向右旋轉 3 步:0->1->2->NULL向右旋轉 4 步:2->0->1->NULL
演算法過程：
思路一：繞圈法。
觀察示例可知，所謂翻轉這個連結串列，無非就是把後幾個節點挪到前面罷了。容易聯想到不過是形成1個圓，然後把新的頭返回即可
1）數節點個數
2）連線首尾節點
3）運動到新的頭部節點的上一位，斷開連結串列
4）返回新的頭部節點
程式碼：
# 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
#先數連結串列有幾個節點
i = head
count = 1
while i.next is not None:
i = i.next
count = 1
#拋掉重複的轉圈,也算一種演算法優化吧
k = k%count
if (k == 0) or count == 1:
return head
#把連結串列頭尾連起來
i.next = head
#從dummy開始運動
i = dummy
#運動到新的連結串列的頭的上一個節點
for _ in range(count - k):
i = i.next
j = i.next
i.next = None
return j
思路二：快慢指標
演算法過程
1）定義2個指標，一快一慢
2）快的先走k步，慢的不動
3）接著快慢一起動，當快的走到節點的時候，慢的的下一項就是新的頭部節點。
演算法證明：
由過程可知，快的永遠比慢的快k步，所以當快的指標到尾部節點時，慢的指標距它還有k步遠。這時候我們從這裡斷開連結串列，則能保證後k個節點移到前面來
程式碼：
class Solution(object):
def rotateRight(self, head, k):
if not head or not head.next or k==0:
return head
ListLen = 0
p = head
#數有幾個節點
while(p):
ListLen =1
p = p.next
#優化
k = k%ListLen
if k==0:
return head
#快節點先走k步
p = head
while(k>0):
k -=1
p = p.next
slow = head
fast = p
#接著讓fast走到最後一個節點，slow與它有著同樣的速度
while fast.next:
slow = slow.next
fast = fast.next
#把頭尾連起來然後斷開連結串列
new_head = slow.next
fast.next = head
slow.next = None
return new_head
總結：快慢指標，可以達到錯位運動的效果，有時能製造很多trick魔法。