我创建了一个可以反转链表的函数，但是发生了一些奇怪的事情，我一直无法弄清楚。
我正在尝试就地编辑列表以节省空间，因此该方法更改了原始列表对象并且不返回任何内容。这意味着如果reverse_list方法的最后一行是(为清楚起见，变量在此处重命名(：
original_first_node.val = new_first_node.val
original_first_node.next = new_first_node.next
但出于某种原因，original_first_node.next上的节点链看起来与new_first_node.next的节点链不同，现在也是周期性的。
下面是一些单元测试失败的可运行代码(请参阅reverse_list函数中的注释(：
import unittest
class Node(object):
def __init__(self, x):
self.val = x
self.next = None
def create_list(list):
if not list:
return None
sentinel = Node(None)
current = sentinel
for item in list:
current.next = Node(item)
current = current.next
return sentinel.next
def convert_list(head):
ret = []
if head:
current = head
while current:
ret.append(current.val)
current = current.next
return ret
def is_list_cyclic(head):
if not head:
return False
tortoise = hare = head
while hare.next and hare.next.next:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return True
return False
def reverse_list(head):
if not head or not head.next:
return
current = head
prev = None
while current:
static_next = current.next
current.next = prev
prev = current
current = static_next
# At this point, prev.next looks great
head.val = prev.val
head.next = prev.next
# head.next is cyclical now for some reason ??
class TestSuite(unittest.TestCase):
def test_reverse_list(self):
head = create_list([1, 2, 3, 4])
reverse_list(head)
self.assertFalse(is_list_cyclic(head))
self.assertEqual([4, 3, 2, 1], convert_list(head))
if __name__ == "__main__":
unittest.main()
这篇 Stackoverflow 帖子包含有关 Python 中参数传递的良好信息： 如何通过引用传递变量？
reverse_list函数中的以下两行是问题所在：
head.val = prev.val
head.next = prev.next
以下是我认为正在发生的事情：
# Marker 1
head.val = prev.val
head.next = prev.next
# Marker 2
在Marker 1中，列表如下所示：
None <--- 1 <--- 2 <--- 3 <--- 4
^ ^
| |
head prev
在Marker 2中，列表如下所示：
----------------------
| |
| |
| v
--- 4 <--- 2 <--- 3 <--- 4
^ ^
| |
head prev
因此，在reverse_list末尾，head仍然指向第一个节点，但它的值4。并且head.next指向包含3的节点，因此您可以获得如图所示的循环。
我的建议是返回对反向列表的第一个节点的引用。修改后的reversed_list如下所示：
def reverse_list(head):
if not head or not head.next:
return
current = head
prev = None
while current:
static_next = current.next
current.next = prev
prev = current
current = static_next
return prev
您的测试可以修改为：
class TestSuite(unittest.TestCase):
def test_reverse_list(self):
head = create_list([1, 2, 3, 4])
rev = reverse_list(head)
self.assertFalse(is_list_cyclic(rev))
self.assertEqual([4, 3, 2, 1], convert_list(rev))
编辑
@mattalxndr，在阅读您的评论时，主要问题似乎是如何在不返回值的情况下"就地"反转列表。我能想到的最简单的解决方案是：
- 列表副本的制作(保存到
copied_list( - 反向
copied_list - 开始遍历从左到右的原始列表
- 开始从右到左遍历
copied_list - 将
val从copied_list复制到原始列表
此技术创建列表的另一个副本，因此使用 O(n( 空间。可能存在更好的算法，但我现在想不出任何算法。