Python資料結構之翻轉鍊錶

翻轉一個鍊錶

範例：給一個鍊錶1->2->3->null，這個翻轉後的鍊錶為3- >2->1->null

#一種比較簡單的方法是用「摘除法」。就是先新建一個空節點，然後遍歷整個鍊錶，依序令遍歷到的節點指向新建鍊錶的頭節點。

那樣例來說，步驟是這樣的：

1. 新建空節點：None
2. 1->None
3. 2->1->None
4. 3->2->1->None

程式碼就非常簡單了：

#

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  temp = None 
  while head: 
   cur = head.next 
   head.next = temp 
   temp = head 
   head = cur 
  return temp 
  # write your code here

當然，還有一個稍微難度更高的解法。我們可以對鍊錶中節點依序摘鍊和連結的方法寫出原地翻轉的程式碼：

#

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  if head is None: 
   return head 
  dummy = ListNode(-1) 
  dummy.next = head 
  pre, cur = head, head.next 
  while cur: 
   temp = cur 
   # 把摘链的地方连起来 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here

##要注意的是，做摘鏈的時候，不要忘了把摘除的地方再連起來

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

更多Python資料結構之翻轉鍊錶相關文章請關注PHP中文網！