反转链表，同时保留原始顺序

Question

我想将链表head反转为新的反转喜欢列表。我能够反转列表，但这样做，原始列表head也会受到影响，head.next变得None。

def reverse(head): 
prev = None
current = head 
while(current is not None): 
next = current.next
current.next = prev 
prev = current 
current = next 

最初： 头 ：-1-->2-->3-->4-->None

反转后： 头 ：-1-->None上一页 ：-4-->3-->2-->1-->None

我基本上希望头部1-->2-->3-->4-->None.

这是链表反转的代码：-

class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_llist(head):
while (head):
print(head.data)
head = head.next
def reverse(head):
prev = None
current = head
while (current is not None):
next = current.next
current.next = prev
prev = current
current = next
return prev

llist = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
llist.next = second
second.next = third
third.next = fourth
# print original list
print("Original:")
print_llist(llist)
# print reversed list
print("Reversed")
print_llist(reverse(llist))
# print original list
print("Original:")
print_llist(llist)

输出：-

Original:
1
2
3
4
Reversed
4
3
2
1
Original:
1

预期产出：-

Original:
1
2
3
4
Reversed
4
3
2
1
Original:
1
2
3
4

Answer 1

在 while 循环结束后添加current.next=prev。并将 while 循环条件更改为while(current.next is not None):

从函数中返回current，而不是prev。此外，添加一个条件以查看head是否None。

所以你的函数变成如下

def reverse(head):
if head is None:
return head
prev=None
current=head
while(current.next is not None):
next=current.next
current.next=prev
prev=current
current=next
current.next = prev
return current

Answer 2

首先写Node，以便你可以在构造函数中传递data和next-

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

这允许我们写 -

mylist = Node(1, Node(2, Node(3, Node(4))))

你也会看到我们如何在reverse中使用Node的第二个参数 -

def reverse(llist):
def loop (r, node):
if node is None:
return r
else:
return loop (Node(node.data, r), node.next)
return loop (None, llist)

请注意我们如何构造一个新Node，而不是使用node.data = ...或node.next = ...修改node。递归优雅地表达解决方案，无需改变原始输入。

我们也可以使用递归将链表转换为字符串 -

def to_str(node):
if node is None:
return "None"
else:
return f"{node.data} -> {to_str(node.next)}"
print(to_str(mylist))
# 1 -> 2 -> 3 -> 4 -> None

让我们验证reverse不会改变原始链表-

mylist = Node(1, Node(2, Node(3, Node(4))))
revlist = reverse(mylist)
print(to_str(mylist))
# 1 -> 2 -> 3 -> 4 -> None
print(to_str(revlist))
# 4 -> 3 -> 2 -> 1 -> None
print(to_str(mylist))
# 1 -> 2 -> 3 -> 4 -> None

---

与您的问题无关，但您可能会认为直接在Node上实现__str__更"pythonic"，以便您可以使用print输出链表 -

class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
def __str__(self):
return f"{self.data} -> {self.next}"

现在用户不需要手动使用to_str或print_llist-

mylist = Node(1, Node(2, Node(3, Node(4))))
print(mylist)
# 1 -> 2 -> 3 -> 4 -> None
print(reverse(mylist))
# 4 -> 3 -> 2 -> 1 -> None