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 

需要注意的是，做摘链的时候，不要忘了把摘除的地方再连起来

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！