链表之反转链表

 1 # 假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
 2 # 在遍历列表时，将当前节点的 next 指针改为指向前一个元素。
 3 # 由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
 4 class LinklistNode:
 5     def __init__(self, x):
 6         self.value = x
 7         self.next = None
 8         
 9 # class Solution:
10     # def reverse_linklist(self, head):
11         # # 首先定义三个指针
12         # pre = None  # 用于指向反转前的链表当前位置的前一个位置的元素，此处赋值None是作为反转后链表的尾结点
13         # cur = head  # 用于指向当前节点
14         # lat = cur.next  # 反转之后，当前节点会与前后的元素都会失去联系，因此后面一个位置也要进行存储，
15         
16         # while lat != None:
17             # cur.next = pre  # 反
18             # pre = cur  # 接下来三个语句实现往前的移动
19             # cur = lat
20             # lat = lat.next
21             
22         # cur.next = pre
23         # return cur  # 因为我们的判断条件是lat != None，当条件不满足的时候，当前节点cur自然就是翻转后的列表的头节点
24         
25 # 但是上述代码存在一个重大bug，如果head = None，那么lat = lat.next就会出问题。
26 class Solution:
27     def reverse_linklist(self, head):
28         pre = None
29         cur = head
30         
31         while cur != None:
32             lat = cur.next
33             cur.next = pre
34             pre = cur
35             cur = lat
36             
37         return pre  # 因为判断条件为cur != None，所以当不满足条件时cur到达了None节点，所以pre所指向的就是翻转后的链表的头节点