单向链表的反转 python,单链表的反转算法

　　本文主要详细介绍python逆向单链表算法。本文中的示例代码非常详细，具有一定的参考价值。感兴趣的朋友可以参考一下。

　　现在算法是大厂面试的必答题，越来越难了。它不再是一个简单的列表，字符串操作将涉及各种数据结构。单链表的倒排也是一个常问的问题，所以记录在这里。

1.链表的特点：

　　元素是顺序存储的，但是元素在空间上是不连续的，所以链表中的每个元素不仅会存储元素的值，还会存储下一个元素的地址。在单链表的情况下，将只有一个指向下一个元素的指针，而在双链表的情况下，将有一个指向前一个元素的指针。因为链表上面的存储特性，在插入和删除的时候，只需要断开指针，不需要移动后面的数据，所以修改链表的效率会很高，但是搜索的效率会很低，这就是链表和数组的区别。链表的存储图：

　　至少有3种方法可以解决这个问题：

　　1.先删除原链表头，再插入新链表头；

　　2.由三个指针实现，p0是上一个节点的指针，p1是当前节点的指针，p2是下一个节点的指针。

　　3.递归实现；

2.方式一：

　　1)创建一个新的空列表；

　　2)取出旧链表中头节点的元素，将其下一个指针设置为新链表的头指针，在旧链表的头节点执行下一个元素。

　　3)依次重复步骤2)的操作，直到取出链表中的所有节点。

　　4)最后，新的链表如下，实现了倒排的功能：

　　5)代码实现：

　　#编码=utf-8

　　导入副本

　　类别节点：

　　节点类，包含值和指向下一个节点的指针

　　def __init__(self，value，next=None):

　　自我价值=价值

　　self.next=下一个

　　def __str__(self):

　　return 节点值：%s % self.value

　　类链接列表：

　　def __init__(self，head=None，tail=None):

　　self.head=头

　　self.tail=尾巴

　　def get_all(self):

　　获取链接列表中的所有节点

　　节点=[]

　　temp=self.head

　　而温度：

　　nodes.append(临时值)

　　temp=temp.next

　　返回节点

　　def add_node(自身，值):

　　将节点添加到列表中。

　　节点=节点(值)

　　#空链表，结束指针都指向新添加的节点。

　　如果self.head为None:

　　self.head=node

　　self.tail=node

　　else:

　　self.tail.next=node

　　self.tail=node

　　def reverse_list(自身):

　　反转单向列表

　　思路一：先删除原来的链表，再插入新的链表。

　　#定义新的链接列表

　　new_list_node=LinkedList()

　　temp=copy.deepcopy(self.head)

　　而温度：

　　# 1.删除上一个链表的头。

　　节点=温度

　　temp=temp.next

　　# 2.在新的链表上执行头插入操作。

　　如果新列表节点头不是：

　　新列表节点。尾=节点

　　node.next=新列表节点

　　新列表节点. head=节点

　　返回新列表节点

　　如果__nam

　　e__ == "__main__":

　　    l = LinkedList()

　　    for i in range(5):

　　        l.add_node(i)

　　    new_list_node = l.reverse_list()

　　    print(new_list_node.get_all())

　　    print(new_list_node.tail)

3.方式二

　　借助3个指针来实现反转，p0之前前一个节点，p1指向当前操作的节点，p2指向下一个节点。操作过程如下：将p1的next指针之前p0，之后将p0指向p1节点，p1指向p2节点，如果p1不为空，重复以上操作，最后，p0即为新列表的头节点。

　　1）开始时p0为空；将p1指向链表的头节点，p1节点的next指针指向p0；p2指向下一个节点：

　　2）调整3个指针的指向：将p0指向p1；p1指向p2，p1的next指向p0；p2指向下一个节点

　　3）循环执行以上步骤，直到p1指向的节点不为空，最后得到的链表为：

　　4）代码实现：

# encoding=utf-8
　　import copy
　　class Node:
　　    """节点类，包含值和下一个节点的指针"""
　　    def __init__(self, value, next=None):
　　        self.value = value
　　        self.next = next
　　    def __str__(self):
　　        return "Node value:%s" % self.value
　　class LinkedList:
　　    def __init__(self, head=None, tail=None):
　　        self.head = head
　　        self.tail = tail
　　    def get_all(self):
　　        """获取链表中所有的节点"""
　　        nodes = []
　　        temp = self.head
　　        while temp:
　　            nodes.append(temp.value)
　　            temp = temp.next
　　        return nodes
　　    def add_node(self, value):
　　        """在列表中添加节点"""
　　        node = Node(value)
　　        # 空链表,收尾指针都指向新增加的节点
　　        if self.head is None:
　　            self.head = node
　　            self.tail = node
　　        else:
　　            self.tail.next = node
　　            self.tail = node
　　    def reverse_list(self):
　　        """
　　        反转单向列表
　　        思路二：通过3个指针实现，p0指向前一个节点的指针，p1表示当前节点的指针，p2表示下一个节点的指针
　　        :return: LinkedList 对象
　　        """
　　        p1 = copy.deepcopy(self.head)
　　        p2 = p1.next
　　        # 定义一个新的链表对象
　　        new_list_node = LinkedList()
　　        while p1:
　　            if new_list_node.head is None:
　　                new_list_node.tail = p1
　　            # 将p1的next指向新链表的头结点
　　            p1.next = new_list_node.head
　　            # 将新链表的头结点指向p1
　　            new_list_node.head = p1
　　            # 将p1指向p2
　　            p1 = p2
　　            # 判断p2是否指向了链表的末尾
　　            if p2:
　　                p2 = p2.next
　　        return new_list_node
　　if __name__ == "__main__":
　　    l = LinkedList()
　　    for i in range(5):
　　        l.add_node(i)
　　    new_list_node = l.reverse_list()
　　    print(new_list_node.get_all())
　　    print(new_list_node.tail)

4.方式三：

　　递归就是将问题分解为处理过程一致的子问题进行处理，但是一定要要结束条件。链表的反转也可以采用递归的方式实现，每次传入的节点不是最后一个的话，就将下一个节点作为参数传递进去，递归调用；直到传入的是最后一个节点时开始逐级返回。

　　1）将链表中每个节点作为参数，依次传入到reverse_list函数中；

　　2）当传入的是最后一个节点时，以此节点为头结点创建一个新的链表，并将此链表返回；

　　3）上一级的调用者接受到返回的链表后，将传入的节点作为链表的尾结点放到链表中；

　　4）逐级返回，直到回到最开始执行reverse_list函数中，将生成的新链表返回即可

　　5）代码实现：

# encoding=utf-8
　　import copy
　　class Node:
　　    """节点类，包含值和下一个节点的指针"""
　　    def __init__(self, value, next=None):
　　        self.value = value
　　        self.next = next
　　    def __str__(self):
　　        return "Node value:%s" % self.value
　　class LinkedList:
　　    def __init__(self, head=None, tail=None):
　　        self.head = head
　　        self.tail = tail
　　    def get_all(self):
　　        """获取链表中所有的节点"""
　　        nodes = []
　　        temp = self.head
　　        while temp:
　　            nodes.append(temp.value)
　　            temp = temp.next
　　        return nodes
　　    def add_node(self, value):
　　        """在列表中添加节点"""
　　        node = Node(value)
　　        # 空链表,收尾指针都指向新增加的节点
　　        if self.head is None:
　　            self.head = node
　　            self.tail = node
　　        else:
　　            self.tail.next = node
　　            self.tail = node
　　    def reverse_list(self, node):
　　        """
　　        反转单链表
　　        思路三：用递归实现
　　        :return:LinkedList 对象
　　        """
　　        if node.next is None:
　　            return LinkedList(node, node)
　　        temp = copy.deepcopy(node)
　　        # 断开当前节点的连接
　　        temp.next = None
　　        # 将当前节点放到内层递归返回的链表结尾
　　        l = self.reverse_list(node.next)
　　        l.tail.next = temp
　　        l.tail = temp
　　        return l
　　if __name__ == "__main__":
　　    l = LinkedList()
　　    for i in range(5):
　　        l.add_node(i)
　　    new_list_node = l.reverse_list1()
　　    print(new_list_node.get_all())
　　    print(new_list_node.tail)

　　以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。