Python 将链表反转的代码|极客笔记

Python 将链表反转的代码

在本教程中，我们将编写Python代码来反转链表。链表用于动态存储元素。链表是一种线性数据结构，类似于数组，但它以动态方式存储元素。每个元素使用特定地址连接到其前一个节点，并存储值以及下一个元素的地址。整个元素称为节点。

在这里，我们将使用Python程序反转给定的链表。让我们理解问题陈述。

问题陈述 –

我们需要提供链表并返回它的反转结果如下。

Input :  1-> 2-> 3-> 4-> NULL
Output : 4-> 3-> 2-> 1-> NULL

Input :  1-> 2-> 3-> 4-> 5-> NULL
Output : 5-> 4-> 3-> 2-> 1->NULL

Input : NULL
Output : NULL

让我们实现给定问题的解决方案。

方法 – 1

首先，我们将创建链表并使用迭代方法解决此问题。

代码 – 创建链表

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        newNode = Node(data)
        if self.head != None:
            current = self.head
            while (current.next):
                current = current.next
            current.next = newNode
        else:
            return None

    def reverse_Llist(self):


    def print_list(self):
        if self.head is not None:
            current = self.head
            while current:
                print(current.data, "->", end = '')
                current = current.next

n = LinkedList()
n.head = Node(1)
n1 = Node(2)
n.head.next = n1
n2 = Node(3)
n1.next = n2
n3 = Node(4)
n2.next = n3

n.print_list()

输出:

1  -> 2  -> 3  -> 4  ->

在以上代码中，我们初始化了链表并添加了一些元素。现在，我们将实现链表的迭代反转方法。

反转链表

我们想要实现 reverse() 方法，它执行以下操作：

所有链接的指向方向相反。
头指针指向链表的最后一个元素。

我们将定义三个指针：

previous – 这是一个初始指针，起始时指向 None ，该指针指向前一个元素，从而可以使用它来反转 next 链接。
current – 它最初指向头部，被这个变量指向的节点的node.next被设置为列表中的前一个项。
after – 它指向第二个节点。我们将它移动到一个元素头部，直到它获得 next==None

让我们实现reverse_Llist()函数。

示例

def reverse_Llist(Llist):
    if Llist.head == Node:
        return None

    previous = None
    current = Llist.head
    after = current.next 

    while current:
        # Reverse the link
        current.next = previous
        # Moving previous element to one ahead
        previous = current
        # Moving current one element ahead
        current = after
        # Moving one element ahead
        if after:
            after = after.next

    Llist.head = previous

n = LinkedList()
n.head = Node(1)
n1 = Node(2)
n.head.next = n1
n2 = Node(3)
n1.next = n2
n3 = Node(4)
n2.next = n3
print("The reverse linked list is: ")
reverse_Llist(n)
n.print_list()

输出：

The reverse linked list is: 
4  -> 3  -> 2  -> 1  ->

解释 –

在上面的代码中，我们初始化了链表实例并创建了链表。调用reverse_Llist()函数来反转链表。

方法 -2 – 递归方法

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        newNode = Node(data)
        if self.head != None:
            current = self.head
            while (current.next):
                current = current.next
            current.next = newNode
        else:
            return None
    def recusive_reverse(self, current, previous):

        # If last node mark it head
        if current.next is None:
            self.head = current

            # Update next to prev node
            current.next = previous
            return

        # Save curr.next node for recursive call
        after = current.next

        # And update next
        current.next = previous

        self.recusive_reverse(after, current)

    def reverse(self):
        if self.head is None:
            return
        self.recusive_reverse(self.head, None)

    def print_list(self):
        if self.head is not None:
            current = self.head
            while current:
                print(current.data, " -> ", end = '')
                current = current.next

输出:

The reverse linked list is: 
4  -> 3  -> 2  -> 1  ->

时间复杂度：O(N)

辅助空间：O(1)

结论

在上面的教程中，我们实现了反转链表问题的解决方案。这是链表的一个重要概念，可能会在面试题中被提问。我们使用迭代和递归方法解决了这个问题，无论使用哪种方法，时间复杂度都是相同的。

Python 将链表反转的代码