欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python數(shù)據(jù)結(jié)構(gòu)之翻轉(zhuǎn)鏈表

 更新時(shí)間：2017年02月25日 08:37:23   投稿：lqh  
這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)之翻轉(zhuǎn)鏈表的相關(guān)資料,需要的朋友可以參考下

翻轉(zhuǎn)一個(gè)鏈表

樣例：給出一個(gè)鏈表1->2->3->null，這個(gè)翻轉(zhuǎn)后的鏈表為3->2->1->null

一種比較簡(jiǎn)單的方法是用“摘除法”。就是先新建一個(gè)空節(jié)點(diǎn)，然后遍歷整個(gè)鏈表，依次令遍歷到的節(jié)點(diǎn)指向新建鏈表的頭節(jié)點(diǎn)。

那樣例來(lái)說(shuō)，步驟是這樣的：

1. 新建空節(jié)點(diǎn)：None
2. 1->None
3. 2->1->None
4. 3->2->1->None

代碼就非常簡(jiǎn)單了：

""" 
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

當(dāng)然，還有一種稍微難度大一點(diǎn)的解法。我們可以對(duì)鏈表中節(jié)點(diǎn)依次摘鏈和鏈接的方法寫(xiě)出原地翻轉(zhuǎn)的代碼：

""" 
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 
   # 把摘鏈的地方連起來(lái) 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here

需要注意的是，做摘鏈的時(shí)候，不要忘了把摘除的地方再連起來(lái)

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

相關(guān)文章

最新評(píng)論