Leetcode 061 旋轉連結串列 python (多解法)

NO IMAGE

一步一個腳印的python leetcode 題解。本人一直在努力地積累Leetcode上用Python實現的題,並且會盡力講清每道題的原理,絕不像其他某些部落格簡略地帶過。
如果覺得講的清楚,歡迎關注。

 

題目描述:

給定一個連結串列,旋轉連結串列,將連結串列每個節點向右移動 個位置,其中 是非負數。

示例 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魔法。