我现在正在组中反转链表，但遇到了一些问题。
问题是：
给定一个具有"n"个节点的LinkedList，按照以下方式根据其大小对其进行反转：
如果"n"是偶数，则在一组n/2个节点中反转列表。如果n是奇数，保持中间节点不变，反转前'n/2'个节点，然后反转最后一个"n/2"节点。
我的方法是：
def lenLinkedlist(head):
count = 0
current = head
while current:
current = current.next
count += 1
return count
def reverseInGroupPart(head, n):
count = 0
previous, current, next = None, head, None
while current and count < n//2:
next = current.next
current.next = previous
previous = current
current = next
count += 1
# even
if n%2 == 0:
# current at middle right now
# head supports to be middle now
head.next = reverseInGroupPart(current, n)
# odd
else:
# current at middle now
head.next = current
current.next = reverseInGroupPart(current.next, n)
return previous
def reverseGroups(head):
n = lenLinkedlist(head)
if n%2 == 0:
return reverseInGroupPart(head, n)
else:
return reverseInGroupPart(head, n)
class Node:
def __init__(self, _value, _next = None):
self.value = _value
self.next = _next
def print_list(self):
temp = self
while temp:
print(temp.value, end = ' ')
temp = temp.next
print()
def main():
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)
print('original linked list is: ', end = '')
head.print_list()
result = reverseGroups(head)
print('reverse of linked list is ', end = '')
result.print_list()
main()
有错误：
Traceback (most recent call last):
File "/Users/PycharmProjects/tester/main.py", line 62, in <module>
main()
File "/Users/PycharmProjects/tester/main.py", line 58, in main
result = reverseGroups(head)
File "/Users/PycharmProjects/tester/main.py", line 33, in reverseGroups
return reverseInGroupPart(head, n)
File "/Users/PycharmProjects/tester/main.py", line 22, in reverseInGroupPart
head.next = reverseInGroupPart(current, n)
File "/Users/PycharmProjects/tester/main.py", line 22, in reverseInGroupPart
head.next = reverseInGroupPart(current, n)
File "/Users/PycharmProjects/tester/main.py", line 22, in reverseInGroupPart
head.next = reverseInGroupPart(current, n)
[Previous line repeated 993 more times]
File "/Users/PycharmProjects/tester/main.py", line 19, in reverseInGroupPart
if n%2 == 0:
RecursionError: maximum recursion depth exceeded in comparison
original linked list is: 1 2 3 4 5 6
Process finished with exit code 1
我尝试使用递归方法来解决这个问题，但不确定是什么原因导致了错误。谢谢
您的reverseGroups()函数没有多大意义，因为它有一个在两个分支中做相同事情的if。
我将采取不同的方法。首先，我将把函数改为Node的方法。接下来，我将使这些方法中的大多数是递归的，只是为了练习。最后，我将使链表分段的反转递归，但不是重新排列链表部分的更高级别逻辑，因为这似乎不是递归问题：
class Node:
def __init__(self, value, _next=None):
self.value = value
self.next = _next
def printLinkedlist(self):
print(self.value, end=' ')
if self.next:
self.next.printLinkedlist()
else:
print()
def lengthLinkedlist(self):
count = 1
if self.next:
count += self.next.lengthLinkedlist()
return count
def reverseLinkedList(self, length):
head, rest = self, self.next
if length > 1:
if rest:
head, rest = rest.reverseLinkedList(length - 1)
self.next.next = self
self.next = None
return head, rest
def reverseGroups(self):
head = self
length = self.lengthLinkedlist()
if length > 3:
tail = self
head, rest = self.reverseLinkedList(length//2) # left
if length % 2 == 1: # odd, skip over middle
tail.next = rest
tail = tail.next
rest = tail.next
tail.next, _ = rest.reverseLinkedList(length//2) # right
return head
if __name__ == '__main__':
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)
head.next.next.next.next.next.next = Node(7)
print('original linked list is: ', end='')
head.printLinkedlist()
head = head.reverseGroups()
print('reverse of linked list is ', end='')
head.printLinkedlist()
输出
> python3 test.py
original linked list is: 1 2 3 4 5 6 7
reverse of linked list is 3 2 1 4 7 6 5
>
如果我们评论掉最后一个链接：
# head.next.next.next.next.next.next = Node(7)
那么我们的输出是：
> python3 test.py
original linked list is: 1 2 3 4 5 6
reverse of linked list is 3 2 1 6 5 4
>
对我来说，这个问题是一个谨慎的记账问题。我还必须首先迭代地实现reverseLinkedList()，使reverseGroups()工作，然后返回并递归地重新实现reverseLinkedList()。
我会逐步解决这个问题。对于初学者来说，类结构可能需要进行一些彻底的修改，以使其更容易使用。我会创建一个LinkedList类，并利用像__repr__、__len__和__iter__这样的dunder方法使代码更干净、更Python。根据PEP-8使用snake_case而不是camelCase。
from functools import reduce
class Node:
def __init__(self, value, next_=None):
self.value = value
self.next = next_
def __repr__(self):
return str(self.value)
class LinkedList:
def __init__(self, els):
self.head = None
for e in reversed(els):
self.head = Node(e, self.head)
def __iter__(self):
curr = self.head
while curr:
yield curr
curr = curr.next
def __getitem__(self, i):
try:
return list(zip(self, range(i + 1)))[-1][0]
except IndexError:
raise IndexError(i)
def __len__(self): # possibly better to cache instead of compute on the fly
return reduce(lambda a, _: a + 1, self, 0)
def __repr__(self):
return "[" + "->".join([str(x) for x in self]) + "]"
if __name__ == "__main__":
for length in range(8):
ll = LinkedList(list(range(length)))
print("original:", ll)
在深入研究算法之前，我应该注意到链表不适合递归(除非语言是尾调用优化的(，因为每个递归步骤只会将问题空间减少1个节点。这会导致大量的调用开销，如果列表中的元素超过1000个，并且通常不会提供太多优雅/可读性来抵消这些缺点，那么就有可能破坏堆栈。
另一方面，树更适合递归，因为在遍历平衡良好的树时，调用堆栈会频繁弹出，使深度保持在对数而不是线性范围内。使用quicksort或mergesort对列表进行排序或执行二进制搜索也是如此。
链表算法还倾向于需要对上一个和下一个节点的许多引用，以及用于伪头和伪尾的记账节点，这些状态在离散堆栈框架中不容易访问。迭代地，您可以直接从循环块访问所需的所有状态，而无需参数。
也就是说，这里有一个简单的迭代反转例程，我将使用它作为编写其余代码的基础：
class LinkedList:
# ...
def reverse(self):
prev = None
curr = self.head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
self.head = prev
这需要变得更通用：如果我可以重构该算法，在节点和子列表长度之间反转列表的子集，那么问题就基本解决了，因为我们可以将该算法分别应用于列表的前半部分和后半部分。
实现这一点的第一步是避免对self.head进行硬编码，并将其作为参数传入，为反转的子列表返回新的头。这仍然存在(我认为这是一项要求(：
class LinkedList:
# ...
def _reverse_from(self, curr):
prev = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
def reverse(self):
self.head = self.reverse_from(self.head)
接下来，我们可以添加一个索引计数器，以启用从节点开始的链表子集的反转。
为了实现这一点，需要将新的尾部节点(子列表的旧前部节点(链接到反向子部分之后的列表后部，否则我们将使用指向None的旧头部/新尾部节点并切掉尾部。
class LinkedList:
# ...
def _reverse_from(self, start, length=-1):
curr = start
prev = None
while curr and length != 0:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
length -= 1
if start:
# link the new tail (old head) with the back of the list
start.next = curr
return prev
最后，添加面向客户端的功能，分别反转每一半：
class LinkedList:
# ...
def reverse_halves(self):
length = len(self)
if length < 4:
return
mid_idx = length // 2
self.head = self._reverse_from(self.head, mid_idx)
if length % 2 == 0:
mid_idx -= 1
mid = self[mid_idx]
mid.next = self._reverse_from(mid.next)
将所有这些与样本运行放在一起，我们得到：
from functools import reduce
class Node:
def __init__(self, value, next_=None):
self.value = value
self.next = next_
def __repr__(self):
return str(self.value)
class LinkedList:
def __init__(self, els):
self.head = None
for e in reversed(els):
self.head = Node(e, self.head)
def _reverse_from(self, start, length=-1):
curr = start
prev = None
while curr and length != 0:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
length -= 1
if start:
start.next = curr
return prev
def reverse(self):
self.head = self._reverse_from(self.head)
def reverse_halves(self):
length = len(self)
if length < 4:
return
mid_idx = length // 2
self.head = self._reverse_from(self.head, mid_idx)
if length % 2 == 0:
mid_idx -= 1
mid = self[mid_idx]
mid.next = self._reverse_from(mid.next)
def __iter__(self):
curr = self.head
while curr:
yield curr
curr = curr.next
def __getitem__(self, i):
try:
return list(zip(self, range(i + 1)))[-1][0]
except IndexError:
raise IndexError(i)
def __len__(self):
return reduce(lambda a, _: a + 1, self, 0)
def __repr__(self):
return "[" + "->".join([str(x) for x in self]) + "]"
if __name__ == "__main__":
for length in range(8):
ll = LinkedList(list(range(length)))
print("original:", ll)
ll.reverse_halves()
print("reversed:", ll, "n")
输出：
original: []
reversed: []
original: [0]
reversed: [0]
original: [0->1]
reversed: [0->1]
original: [0->1->2]
reversed: [0->1->2]
original: [0->1->2->3]
reversed: [1->0->3->2]
original: [0->1->2->3->4]
reversed: [1->0->2->4->3]
original: [0->1->2->3->4->5]
reversed: [2->1->0->5->4->3]
original: [0->1->2->3->4->5->6]
reversed: [2->1->0->3->6->5->4]