python数据结构之翻转链表的步骤

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 

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

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