如何编写递归函数来反转链表? [英] How can I write a recursive function to reverse a linked list?

问题描述

我希望用 Python 来做这件事.而且我不想只是反向打印它，而是实际上反转给定的节点.我已经看到它用其他语言完成，但在 Python 中找不到示例.

我试图在一个函数中完成它，但如果需要一个辅助函数，那就这样吧.

解决方案

def reverse (item, tail = None):下一个 = item.nextitem.next = 尾如果下一个是无:归还物品别的:返回反向(下一个，项目)

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

 类链表:def __init__ (self, value, next = None):self.value = 价值self.next = 下一个def __repr__(自我):返回 '​​LinkedList({}, {})'.format(self.value, repr(self.next))

示例:

<预><代码>>>>a = LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4))))>>>一种LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4, None))))>>>b = 反向(a)>>>乙LinkedList(4, LinkedList(3, LinkedList(2, LinkedList(1, None))))>>>a # 注意现在有一个新的头指针链表(1，无)

I am looking to do it with Python. And I don't want to just print it in reverse, but actually reverse the given nodes. I have seen it done in other languages but had trouble finding an example in Python.

I'm trying to do it in one function, but if a helper function was needed then so be it.

解决方案

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

Using such a simple linked list implementation:

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))

Example:

>>> 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)

这篇关于如何编写递归函数来反转链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！