反转python中的链表

Reversing a linked list in python

提问by Ramya

I am asked to reverse a which takes head as parameter where as head is a linked list e.g.: 1 -> 2 -> 3 which was returned from a function already defined I tried to implement the function reverse_linked_list in this way:

我被要求反转 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

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)

It is called in this way: check_reversal([1,2,3]). The function I have written for reversing the list is giving [3,2,1,2,1,2,1,2,1]and works only for a list of length 3. How can I generalize it for a list of length n?

它是这样调用的：check_reversal([1,2,3])。我为反转列表而编写的函数正在给出[3,2,1,2,1,2,1,2,1]并且仅适用于长度为 3 的列表。如何将其概括为长度列表n？

采纳答案by coderusher

U can use mod function to get the remainder for each iteration and obviously it will help reversing the list . I think you are a student from Mission R and D

你可以使用 mod 函数来获取每次迭代的余数，显然这将有助于反转列表。我想你是Mission R and D的学生

head=None   
prev=None
for i in range(len):
    node=Node(number%10)
    if not head:
        head=node
    else:
        prev.next=node
    prev=node
    number=number/10
return head

回答by Blckknght

The accepted answer doesn't make any sense to me, since it refers to a bunch of stuff that doesn't seem to exist (number, node, lenas a number rather than a function). Since the homework assignment this was for is probably long past, I'll post what I think is the most effective code.

接受的答案对我来说没有任何意义，因为它指的是一堆似乎不存在的东西（number, node,len作为数字而不是函数）。由于这个家庭作业可能已经过去很久了，我将发布我认为最有效的代码。

This is for doing a destructive reversal, where you modify the existing list nodes:

这是为了进行破坏性逆转，您可以在其中修改现有列表节点：

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

A less fancy implementation of the function would use one temporary variable and several assignment statements, which may be a bit easier to understand:

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

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

An alternative design would be to create an entirely new list without changing the old one. This would be more appropriate if you want to treat the list nodes as immutable objects:

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

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

回答by Hyman

I found blckknght's answer useful and it's certainly correct, but I struggled to understand what was actually happening, due mainly to Python's syntax allowing two variables to be swapped on one line. I also found the variable names a little confusing.

我发现 blckknght 的答案很有用，而且肯定是正确的，但我很难理解实际发生的情况，主要是因为 Python 的语法允许在一行上交换两个变量。我还发现变量名称有点混乱。

In this example I use previous, current, tmp.

在这个例子中，我使用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

Taking a singly linked list with 3 nodes (head = n1, tail = n3) as an example.

以具有 3 个节点（head = n1，tail = n3）的单向链表为例。

n1 -> n2 -> n3

n1 -> n2 -> n3

Before entering the whileloop for the first time, previousis initialized to Nonebecause there is no node before the head (n1).

在while第一次进入循环之前，previous被初始化为None因为头（n1）之前没有节点。

I found it useful to imagine the variables previous, current, tmp'moving along' the linked list, always in that order.

我发现想象变量previous, current, tmp“沿着”链表“移动”很有用，总是按照这个顺序。

First iteration

第一次迭代

previous = None

previous = None

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

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

Second iteration

第二次迭代

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

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

Third iteration

第三次迭代

# next is None

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

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

Since the whileloop exits when current == Nonethe new head of the list must be set to previouswhich is the last node we visited.

因为while当current == None必须将列表的新头设置为previous我们访问的最后一个节点时循环退出。

Edited

已编辑

Adding a full working example in Python (with comments and useful strrepresentations). I'm using tmprather than nextbecause nextis a keyword. However I happen to think it's a better name and makes the algorithm clearer.

在 Python 中添加一个完整的工作示例（带有注释和有用的str表示）。我使用tmp而不是next因为next是一个关键字。但是我碰巧认为它是一个更好的名字并且使算法更清晰。

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

    def __str__(self):
        return str(self.value)

    def set_next(self, value):
        self.next = Node(value)
        return self.next


class LinkedList:
    def __init__(self, head=None):
        self.head = head

    def __str__(self):
        values = []
        current = self.head
        while current:
            values.append(str(current))
            current = current.next

        return ' -> '.join(values)

    def reverse(self):
        previous = None
        current = self.head

        while current.next:
            # Remember `next`, we'll need it later.
            tmp = current.next
            # Reverse the direction of two items.
            current.next = previous
            # Move along the list.
            previous = current
            current = tmp

        # The loop exited ahead of the last item because it has no
        # `next` node. Fix that here.
        current.next = previous

        # Don't forget to update the `LinkedList`.
        self.head = current


if __name__ == "__main__":

    head = Node('a')
    head.set_next('b').set_next('c').set_next('d').set_next('e')

    ll = LinkedList(head)
    print(ll)
    ll.revevse()
    print(ll)

Results

结果

a -> b -> c -> d -> e
e -> d -> c -> b -> a

回答by h_vm

Node class part borrowed from interactive python.org: http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

从交互式 python.org 借用的节点类部分：http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

I created the reversed function. All comments in the loop of reverse meant for 1st time looping. Then it continues.

我创建了反向函数。反向循环中的所有评论都意味着第一次循环。然后它继续。

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

  def setData(self,newdata):
    self.d = newdata

  def setNext(self,newnext):
    self.next = newnext

  def getData(self):
    return self.d

  def getNext(self):
    return self.next

class LinkList():
  def __init__(self):
    self.head = None

  def reverse(self):
    current = self.head   >>> set current to head(start of node)
    previous = None       >>>  no node at previous
    while current !=None: >>> While current node is not null, loop
        nextt =  current.getNext()  >>> create a pointing var to next node(will use later)
        current.setNext(previous)   >>> current node(or head node for first time loop) is set to previous(ie NULL), now we are breaking the link of the first node to second node, this is where nextt helps(coz we have pointer to next node for looping)
        previous = current  >>> just move previous(which was pointing to NULL to current node)
        current = nextt     >>> just move current(which was pointing to head to next node)

    self.head = previous   >>> after looping is done, (move the head to not current coz current has moved to next), move the head to previous which is the last node.

回答by Vishal Mishra

I tried a different approach, in place reversal of the LList. Given a list 1,2,3,4

我尝试了一种不同的方法，就地反转 LList。给定一个列表 1,2,3,4

If you successively swap nearby nodes,you'll get the solution.

如果您连续交换附近的节点，您将得到解决方案。

len=3 (size-1)
2,1,3,4
2,3,1,4
2,3,4,1

len=2 (size-2)
3,2,4,1
3,4,2,1

len=1 (size-3)
4,3,2,1

The code below does just that. Outer for loop successively reduces the len of list to swap between. While loop swaps the data elements of the Nodes.

下面的代码就是这样做的。外部 for 循环依次减少要交换的列表的长度。While 循环交换节点的数据元素。

def Reverse(head):
    temp = head
    llSize = 0
    while temp is not None:
        llSize += 1
        temp = temp.next


    for i in xrange(llSize-1,0,-1):
        xcount = 0
        temp = head
        while (xcount != i):
            temp.data, temp.next.data = temp.next.data, temp.data
            temp = temp.next
            xcount += 1
    return head

This might not be as efficient as other solutions, but helps to see the problem in a different light. Hope you find this useful.

这可能不如其他解决方案有效，但有助于从不同的角度看待问题。希望您觉得这个有帮助。

回答by slashdottir

Here is a way to reverse the list 'in place'. This runs in constant time O(n) and uses zero additional space.

这是一种“就地”反转列表的方法。这在恒定时间 O(n) 中运行并使用零额外空间。

def reverse(head):
  if not head:
    return head
  h = head
  q = None
  p = h.next
  while (p):
    h.next = q
    q = h
    h = p
    p = h.next
  h.next = q
  return h

Here's an animation to show the algorithm running.
(# symbolizes Null/None for purposes of animation)

这是一个显示算法运行的动画。
（# 代表 Null/None 用于动画目的）

回答by Justin Malinchak

Here is the whole thing in one sheet. Contains the creation of a linked list, and code to reverse it.

这是一张纸上的全部内容。包含链表的创建，以及反转它的代码。

Includes an example so you can just copy and paste into an idle .py file and run it.

包含一个示例，因此您可以将其复制并粘贴到空闲的 .py 文件中并运行它。

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


def reverse(head):
    temp = head
    llSize = 0
    while temp is not None:
        llSize += 1
        temp = temp.next
    for i in xrange(llSize-1,0,-1):
        xcount = 0
        temp = head
        while (xcount != i):
            temp.value, temp.next.value = temp.next.value, temp.value
            temp = temp.next
            xcount += 1
    return head


def printnodes(n):
    b = True
    while b == True:
        try:
            print n.value
            n = n.next
        except:
            b = False

n0 = Node(1,Node(2,Node(3,Node(4,Node(5,)))))
print 'Nodes in order...'
printnodes(n0)
print '---'
print 'Nodes reversed...'
n1 = reverse(n0)
printnodes(n1)

回答by Yestay Muratov

def reverseLinkedList(head):

    current =  head
    previous = None
    nextNode = None

    while current:

        nextNode = current.nextNode
        current.nextNode = previous

        previous = current
        current = nextNode

    return previous

回答by grepit

Most previous answers are correct but none of them had the complete code including the insert methodbefore and and after the reverse so you could actually see the outputs and compare. That's why I'm responding to this question. The main part of the code of course is the reverse_list() method. This is in Python 3.7 by the way.

以前的大多数答案都是正确的，但没有一个包含完整的代码，包括反向前后的插入方法，因此您可以实际查看输出并进行比较。这就是为什么我要回答这个问题。代码的主要部分当然是 reverse_list() 方法。顺便说一下，这是在 Python 3.7 中。

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


class LinkedList(object):

    def __incurrent__(self, head=None):
        self.head = head

    def insert(self, data):
        tmp = self.head
        self.head = Node(data)
        self.head.next = tmp

    def reverse_list(self):
        current = self.head
        prev = None

        while current :
            #create tmp to point to next
            tmp = current.next
            # set the next to point to previous
            current.next = prev
            # set the previous to point to current
            prev = current
            #set the current to point to tmp
            current = tmp
        self.head = prev


    def print(self):
        current = self.head
        while current != None:
            print(current.data,end="-")
            current = current.next
        print(" ")


lk = LinkedList()
lk.insert("a")
lk.insert("b")
lk.insert("c")

lk.print()
lk.reverse_list()
lk.print()

output:

输出：

c-b-a- 
a-b-c- 

回答by P.R.

Following is the generalized code to reverse a singly linked list, where head is given as function's argument:

以下是反转单链表的通用代码，其中 head 作为函数的参数给出：

def reverseSll(ll_head):
    # if head of the linked list is empty then nothing to reverse
    if not ll_head:
        return False
    # if only one node, reverse of one node list is the same node
    if not ll_head.next:
        return ll_head
    else:
        second = ll_head.next # get the second node of the list
        ll_head.next = None # detach head node from the rest of the list
        reversedLL = reverseSll(second) # reverse rest of the list
        second.next = ll_head # attach head node to last of the reversed list
        return reversedLL

Let me explain what I am doing here:

1) if head is null or head.next is null(only one node left in the list) return node
2) else part: take out 1st node, remove its link to rest of the list, reverse rest of the list(reverseSll(second)) and add 1st node again at last and return the list

Github link for the same

让我解释一下我在这里做什么：

1）如果 head 为空或 head.next 为空（列表中只剩下一个节点）返回节点
2）其他部分：取出第一个节点，删除它与列表其余部分的链接, 反转列表的其余部分(reverseSll(second)) 并最后再次添加第一个节点并返回相同的列表

Github 链接