在不更改原始 LinkedList 的情况下反转单链表

Question

我有两个 .py 文件。

LinkedList.py 拥有定制的 Node class.
script.py 其中包含我的代码来反转 LinkedList

我在 script.py 中导入节点 class：
from LinkedList import *
我在 script.py 中创建了一个名为 reverse_linked_list 的函数，它包含一个名为 linked_list.

的参数

我可以像这样反转 linked_list：

def reverse_linked_list(linked_list):
  prev = None
  current = Node(linked_list).data
  while (current is not None):
    nextNode = current.next
    current.next = prev
    prev = current
    current = nextNode
  current = prev
  return prev

我收到了一些要使用的对象

print("Original")
demo_list = make_linked_list([4,8,15])
demo_list.print_linked_list()
print("Reversed")
reverse = reverse_linked_list(demo_list)
reverse.print_linked_list()
print("Original Unchanged")
demo_list.print_linked_list()

节点 class 的实现如下所示：

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

我试图理解为什么我的代码正在更改“原始列表”，但无法弄清楚原因。我得到的输出是：

Original
4
8
15
Reversed
15
8
4
Original Unchanged
4

我希望“原始未更改”不要更改并保持为“原始”。原始列表在哪里发生变化，为什么？

Answer 1

以下是使驱动程序代码按预期工作的 functions/methods：

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

    def __iter__(self):
        node = self
        while node:
            yield node.data
            node = node.next

    def __repr__(self):
        return "->".join(map(repr, self))
    
    def print_linked_list(self):
        print(self)


def reverse_linked_list(iterable):
    revhead = None
    for data in iterable:
        revhead = Node(data, revhead)
    return revhead

def make_linked_list(values):
    return reverse_linked_list(reversed(values))

请注意 reverse_linked_list 不仅可以从另一个链表创建链表，还可以从任何可迭代对象创建链表。这是因为通过实现 __iter__ 方法使 Node 实例可迭代。

这是您的驱动程序代码，它将生成输出：

print("Original")
demo_list = make_linked_list([4,8,15])
demo_list.print_linked_list()
print("Reversed")
reverse = reverse_linked_list(demo_list)
reverse.print_linked_list()
print("Original Unchanged")
demo_list.print_linked_list()

输出：

Original
4->8->15
Reversed
15->8->4
Original Unchanged
4->8->15

在不更改原始 LinkedList 的情况下反转单链表

Reverse a singly-Linked List without changing the orginal LinkedList

python

algorithm

singly-linked-list