Python 链表反转算法不起作用

发布于08月07日

我正在try 用Python语言编写一个简单的函数来反转链表:

def reverse(head):
    prev = None
    nxt = head.next
    head.next = prev
    while nxt:
        prev = head
        head = nxt
        head.next = prev
        nxt = nxt.next
    return head

当我仔细考虑的时候，这个逻辑似乎是正确的. 首先将prev移动到Head，然后向前移动Head，使其指向与nxt相同的 node ，然后将Head设置在它所在的位置旁边.最终将nxt向前移动一位.迭代，直到nxt到达列表的末尾.

但是，当我try 用以下代码反转链表0-&gt；1-&gt；2-&gt；3-&gt；4-&gt；5时:

def traverse(head):
    while head:
        print(head.val)
        head = head.next

它无休止地重复打印0和1.

推荐答案

正如Michael指出的，您的代码使链表中的第一个和第二个元素彼此指向对方.

解决方法很简单，下面是我所做的:

def reverse(head):
    nxt = head.next
    head.next = None
    while nxt:
        temp1 = nxt.next
        temp2 = head
        head = nxt 
        nxt.next = temp2
        nxt = temp1

这段代码最初做的事情与您的相同.然而，While循环使用2个临时变量temp1和temp2来保存nxt周围的变量的地址(两侧).这可以防止代码中发生的冲突.

希望这个能帮上忙！干杯!