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

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