python反转单链表算法题

现在算法是大厂面试的必考题,而且越来越难,已经不是简单的列表,字符串操作了,会涉及到各种数据结结构。单链表的反转也是经常考的一道题,里面故在此记录一下。

1.链表的特点:

顺序存储元素,但是元素在空间上是不连续的,所以在链表每个元素中除了存储元素的值,还会存储下一个元素的地址,单链表的话就只有指向下一个元素的指针,双向链表的话还会有指向前一个元素的指针。正是由于链表以上的存储特点,在做插入和删除操作时只需要断开指针的连接,不需要移动后面的数据,所以对链表修改的效率会很高,但是查找的效率会很低,这也正是链表和数组的区别。链表的存储示意图:

python反转单链表算法题_第1张图片

完成这道题至少有3种方式:

1.先对原链表做头部删操作,再对新链表做头部插入操作;
2.通过3个指针实现,p0指向前一个节点的指针,p1表示当前节点的指针,p2表示下一个节点的指针
3.用递归实现;

2.方式一:

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

2)取出旧链表中头结点的元素,将其next指针设置为新链表的头指针,同时将旧链表的头结点执行下一个元素

python反转单链表算法题_第2张图片

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

python反转单链表算法题_第3张图片

4)最后形成的新链表如下,实现了反转的功能:

python反转单链表算法题_第4张图片

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):
        """反转单向列表
        思路一:先对原链表做头删操作,再对新链表做头插
        """
        # 定义一个新的链表
        new_list_node = LinkedList()
        temp = copy.deepcopy(self.head)
        while temp:
            # 1.对之前的链表做头删除操作
            node = temp
            temp = temp.next
 
            # 2.对新的链表做头插入操作
            if new_list_node.head is None:
                new_list_node.tail = node
            node.next = new_list_node.head
            new_list_node.head = node
        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)

3.方式二

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

1)开始时p0为空;将p1指向链表的头节点,p1节点的next指针指向p0;p2指向下一个节点:

python反转单链表算法题_第5张图片

2)调整3个指针的指向:将p0指向p1;p1指向p2,p1的next指向p0;p2指向下一个节点

python反转单链表算法题_第6张图片

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

python反转单链表算法题_第7张图片

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.方式三:

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

python反转单链表算法题_第8张图片

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)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

你可能感兴趣的