数据结构：单链表实现反转

悠悠 2021-12-16 14:13 302阅读 0赞

# 实现思路： #

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: 1
    Node: 2
    Node: 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: 3
    Node: 2
    Node: 1

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430113558527.jpg]

[20200430113558527.jpg]: /images/20211214/37a26598c96c4edca3a7c1b8827ddb5a.png