时间戳

首页 > 解决方案 > 反向分组链表

python - 反向分组链表

问题描述

我现在正在研究分组反转链表，但遇到了一些问题。

问题是：

给定一个具有“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

我尝试使用递归方法来解决问题，但不确定是什么导致了错误。谢谢。

标签： pythonrecursionlinked-listreverse

解决方案

您的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()递归地重新实现。

推荐阅读