问

在python中反转链表

灰包蛋啦_199 发布于 2023-01-29 17:14

我被要求反转a以head为参数,其中head是一个链表,例如:1 - > 2 - > 3,它是从已定义的函数返回的,我试图用这种方式实现函数reverse_linked_list:

def reverse_linked_list(head):
temp = head
head = None
temp1 = temp.next
temp2 = temp1.next
temp1.next = None
temp2.next = temp1
temp1.next = temp
return temp2
pass

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

def to_linked_list(plist):
head = None
prev = None
for element in plist:
    node = Node(element)
    if not head:
        head = node
    else:
        prev.next = node
    prev = node
return head

def from_linked_list(head):
result = []
counter = 0
while head and counter < 100: # tests don't use more than 100 nodes, so bail if you loop 100 times.
    result.append(head.value)
    head = head.next
    counter += 1
return result


def check_reversal(input):
    head = to_linked_list(input)
    result = reverse_linked_list(head)
    assert list(reversed(input)) == from_linked_list(result)

它以这种方式调用:check_reversal([1,2,3]).我为反转列表而编写的函数是给出[3,2,1,2,1,2,1,2,1]并仅用于长度为3的列表.如何将其推广为长度列表n？

2 个回答

接受的答案没有任何意义,我,因为它是指一堆东西,似乎不存在(number,node,len为数字而不是函数).由于这项作业可能已经很久了,我会发布我认为最有效的代码.

这是用于执行破坏性反转,您可以在其中修改现有列表节点:

def reverse_list(head):
    new_head = None
    while head:
        head.next, head, new_head = new_head, head.next, head # look Ma, no temp vars!
    return new_head

一个不那么花哨的函数实现将使用一个临时变量和几个赋值语句,这可能更容易理解:

def reverse_list(head):
    new_head = None  # this is where we build the reversed list (reusing the existing nodes)
    while head:
        temp = head  # temp is a reference to a node we're moving from one list to the other
        head = temp.next  # the first two assignments pop the node off the front of the list
        temp.next = new_head  # the next two make it the new head of the reversed list
        new_head = temp
    return new_head

另一种设计是在不改变旧列表的情况下创建一个全新的列表.如果要将列表节点视为不可变对象,这将更合适:

class Node(object):
    def __init__(self, value, next=None): # if we're considering Nodes to be immutable
        self.value = value                # we need to set all their attributes up
        self.next = next                  # front, since we can't change them later

def reverse_list_nondestructive(head):
    new_head = None
    while head:
        new_head = Node(head.value, new_head)
        head = head.next
    return new_head

2023-01-29 17:16 回答

我发现Blckknght的答案很有用,而且肯定是正确的,但我很难理解实际发生了什么,主要是因为Python的语法允许在一行上交换两个变量.我还发现变量名有点令人困惑.

在这个例子中我使用previous, current, tmp.
```
def reverse(head):
    current = head
    previous = None

    while current:
        tmp = current.next
        current.next = previous   # None, first time round.
        previous = current        # Used in the next iteration.
        current = tmp             # Move to next node.

    head = previous
```
以3个节点(head = n1,tail = n3)为例,以单链表为例.

n1 -> n2 -> n3

在while第一次进入循环之前,previous初始化为,None因为head(n1)之前没有节点.

我发现想象变量previous, current, tmp"沿着链表移动"总是按顺序很有用.

第一次迭代

previous = None

[n1] -> [n2] -> [n3] current tmp current.next = previous

第二次迭代

[n1] -> [n2] -> [n3] previous current tmp current.next = previous

第三次迭代
```
# next is None
```
[n1] -> [n2] -> [n3] previous current current.next = previous

由于while循环current == None在列表的新头必须设置为previous我们访问的最后一个节点时退出.
2023-01-29 17:16 回答

qsslidan

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签