如何编写一个递归函数来反转链表？

Question

我希望使用Python来实现这个功能。我不仅仅是想要将其反向打印，而是实际上要反转给定的节点。我已经在其他语言中看到过这样的操作，但是在Python中找到示例有些困难。

我试图在一个函数中完成这个操作，但如果需要一个辅助函数，那就需要这样做。

- Jim John

---

Python太过简单，因此你不会在其中找到任何伟大的例子。你只需使用l[::-1]获取列表l的反转版本，或者（如果你只需要迭代器）使用reversed(l)。顺便说一下，这些是极其基本的东西，因为列表在Python中非常重要。我建议你通读教程，以了解该语言基础知识。 - Carsten

请展示您的代码片段和尝试。 - Łukasz Rogalski

@Carsten 注意，Jim John 正在询问如何反转一个链表，而不是 Python 的 list（它是作为数组实现的）。 - Zero Piraeus

@ZeroPiraeus 哦，我不知道实际的实现方式，谢谢。但我写这个是因为我认为这就是 OP 所寻找的。另一个选择是 OP 让人们在不知道所链接列表的实际实现情况下猜测。 - Carsten

@Carsten，此人在谈论链表而不是列表。 - Mona Jalal

Answer 1

def reverse (item, tail = None):
    next = item.next
    item.next = tail
    if next is None:
        return item
    else:
        return reverse(next, item)

使用这样一个简单的链表实现：

class LinkedList:
    def __init__ (self, value, next = None):
        self.value = value
        self.next = next
    def __repr__ (self):
        return 'LinkedList({}, {})'.format(self.value, repr(self.next))

例子：

>>> a = LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4))))
>>> a
LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4, None))))
>>> b = reverse(a)
>>> b
LinkedList(4, LinkedList(3, LinkedList(2, LinkedList(1, None))))
>>> a # note that there is a new head pointer now
LinkedList(1, None)

- poke

Answer 2

我创建了一个简单的链表实现，其中包含使用递归的反转方法。

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

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

    def isEmpty(self):
        return self.head == None

    def add(self,data): #this method adds node at head
        temp = Node(data)
        temp.setNext(self.head)
        self.head = temp

    def traverse(self):
        current = self.head
        while current:
            if current.getNext():
                print(current.data,end="->")
            else:
                print(current.data)
            current = current.getNext()

    def reverse(self,item):
        if item.next == None:
            self.head = item
            return
        self.reverse(item.next)
        temp = item.next
        temp.next = item
        item.next = None


def main():
    mylist = LinkedList()
    mylist.add(15)
    mylist.add(20)
    mylist.add(25)
    mylist.add(30)
    mylist.traverse()
    mylist.reverse(mylist.head)
    mylist.traverse()
    print(mylist.head.data)

if __name__ == "__main__":
    main()

输出：

Before:
30->25->20->15
After:
15->20->25->30

- Rajat Bhatt

Answer 3

在深入了解如何使用迭代和递归方法反转Python中的链接列表并进行足够的重构后，我编写了这个代码。我研究的许多链接似乎有点不清楚或有不必要的步骤。如果我没有达到最少/清晰的步骤，那么我认为这些步骤至少是接近的。我认为最好不要包含输出，但它将按原样运行并产生输出（python 2.7并易于修改为3.x）。

class Node:
def __init__(self,val):
    self.val = val
    self.next = None # the pointer initially points to nothing

def traverse(self):
    # start from the head node
    node = self 
    while node != None:
        # access the node value
        out_string = 'val = %d, loc = %s, next = %s'
        print out_string % (node.val, node, node.next)
        # move on to the next node
        node = node.next 

def reverse_iteratively(self):
    previous = None
    current = None
    head = self

    while head:
        # before reverse
        previous = current
        current = head
        head = head.next
        # reverse the link
        current.next = previous

def reverse_recursively(self, node, pre=None):
    if node.next != None:
        self.reverse_recursively(node.next, pre=node)
    node.next = pre

### Operation Section
node0 = Node(0)
node1 = Node(7);  node0.next = node1
node2 = Node(14); node1.next = node2
node3 = Node(21); node2.next = node3
node4 = Node(28); node3.next = node4
node5 = Node(35); node4.next = node5
node6 = Node(42); node5.next = node6
node7 = Node(49); node6.next = node7
node8 = Node(56); node7.next = node8
node9 = Node(63); node8.next = node9

print "Forward linked:"
node0.traverse()
node0.reverse_recursively(node0)
print "Reverse linked:"
node9.traverse()

- Thom Ives

Answer 4

递归也可以实现这个功能：

def reverse(head):
  # Empty list is always None
  if not head:
    return None

  # List of length 1 is already reversed
  if not head.get_next():
    return head


  next = head.get_next()

  head.set_next(None)

  rest = reverse(next)

  next.set_next(head)

  return rest

- alex

Answer 5

def reverse_linkedlist(node):
    if node == None or node.next == None:
        return node
    else:
        
        last_node = reverse_linkedlist(node.next)
        new_head = node.next
        new_head.next = node
        node.next = None
        
        return last_node

- Max Eisenhardt

Answer 6

有两种可能的实现方式。

第一种方法不依赖于类属性来保存一旦找到的head。它通过递归调用堆栈返回指向head的指针。

def reverseList(head):
  # Empty list is always None
  if not head:
    return None

  # List of length 1 is already reversed
  if not head.next:
    return head


  next = head.next
  head.next = None
  rest = reverseList(next)
  next.next = head

  return rest

第二种解决方案是，在您的类内使用指向head（类属性）的指针。

class Solution:
head: Optional[ListNode]
    
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    node = head
    
    if node == None:
        return node
    
    if node.next == None:
        self.head = node
        return
    
    
    self.reverseList(node.next)
    q = node.next
    q.next = node
    node.next = None

    return self.head
    

- Shady Smaoui

Answer 7

def reverse_list(self,node):
     if node is None:
         return //list is empty
     elif node.next is None:
        self.head = node // changing the head to last node after reversal
        return
     else:
        reverse_list(node.next) //call the function recursively until the end of the list
        node.next.next = node //reverse the link
        node.next = None

- raviraja

Answer 8

稍作修改，基于 @Rajat Bhatt 实现。区别在于下面的代码可以作为一个单独的函数在链表类之外执行。

print '\n-- Initialize --'
lst = LinkedList(10)    # 10 --> *
print '\n-- Insert --'
lst.append(20)          # 10 --> 20 --> *
lst.append(30)          # 10 --> 20 --> 30 --> *
lst.insertAt(15, pos=1) # 10 --> 15 --> 20 --> 30 --> *
lst.insertAt(25, pos=3) # 10 --> 15 --> 20 --> 25 --> 30 --> *
lst.insertAt(2)         # 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> *
lst.append(100)         # 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> 100 --> *
lst.append(500)         # 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> 100 --> 500 --> *


print lst
# 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> 100 --> 500 --> *

print '\n-- Reverse using Recursion --'
def revFunc(curr):
    if curr.next_node is None:
        lst.head = curr
        return None

    revFunc(curr.next_node)
    curr.next_node.next_node = curr
    curr.next_node = None

revFunc(lst.head)

print lst               
# Head --> 500 --> 100 --> 30 --> 25 --> 20 --> 15 --> 10 --> 2 --> *

- Pradeep Krishnaraj

Answer 9

def reverse_ll_pass(self):

    temp = self.head
    if temp is None:
        return

    return self.reverse_ll_recursive(temp,past=None)

def reverse_ll_recursive(self,curr,past):

    if curr is None:
        self.head = past
        return self.head
    else:
        future = curr.next
        curr.next = past
        past = curr
        curr = future 
        return self.reverse_ll_recursive(curr,past)  

- Jai krish

Answer 10

与poke的解决方案非常相似，但我更喜欢先处理基本情况：

def reverse(head, reversed=None):
    if head is None:
        return reversed
    new_head = head.next
    head.next = reversed
    new_reversed = head
    return reverse(new_head, new_reversed)

- kas