双链表插入图解单链表实现反转

导读实现思路：如果链表只有一个或者没有节点，则无需反转原链表的第一个节点即为反转后的最后一个元素，需要将其固定，我们叫它final按原链表的顺序从第二个开始对所....

实现思路：

1. 如果链表只有一个或者没有节点，则无需反转
2. 原链表的第一个节点即为反转后的最后一个元素，需要将其固定，我们叫它final
3. 按原链表的顺序从第二个开始对所有节点node进行遍历，每次将final的next重新指向node的next， 将node的next重新指向head的next，将head的next重新指向node （head：链表的头节点，不存放实际节点 next：某个节点的下一个节点）
4. 遍历方法需要注意：其实是对final的next进行遍历，直到为None

代码实现

首先，我们新建一个Node类，也就是链表上的节点； 然后，再创建一个LinkedList类，也就是一个单链表类。里面包含了添加节点的add方法和打印整个链表的show方法

class Node: def __init__(self, i): self.id = i self.next = None class LinkedList: def __init__(self): self.head = Node(-1) def add(self, Node): node = self.head while True: if node.next is None: break else: node = node.next node.next = Node def show(self): node = self.head.next while node is not None: print(Node: str(node.id)) node = node.next

我们创建一个链表对象，加入3个节点，如下：

lk = LinkedList()lk.add(Node(1))lk.add(Node(2))lk.add(Node(3))lk.show()​Node: 1Node: 2Node: 3

最后，就是我们实现链表反转的方法，也是类方法。

def reverse(self): final = self.head.next temp = final.next if (final is None) | (temp is None): return while temp is not None: final.next = temp.next temp.next = self.head.next self.head.next = temp temp = final.next

验证一下，我们的反转方法，结果没有问题，就是我们想要的结果。

lk.reverse()lk.show()​Node: 3Node: 2Node: 1