Python資料結構之翻轉連結串列

NO IMAGE

翻轉一個連結串列

樣例:給出一個連結串列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中陣列,列表:冒號的靈活用法介紹(np陣列,列表倒序)Python中字典(dict)和列表(list)的排序方法例項Python中對列表排序例項Python對兩個有序列表進行合併和排序的例子Python中對元組和列表按條件進行排序的方法示例Python實現翻轉陣列功能示例python實現對指定輸入的字串逆序輸出的6種方法Python實現按照指定要求逆序輸出一個數字的方法Python實現字串逆序輸出功能示例Python針對給定列表中元素進行翻轉操作的方法分析