如何在 Python 中反转循环链表

Question

我有一个正在练习的循环链表对象，但我卡在了必须反转循环链表的部分。我可以找到很多使用 Java & C 的示例，但没有 python 示例。我试图从 C 和 Java 程序转换逻辑，但它没有正确输出。它只收集列表的一部分并且似乎提前终止。

这是我到目前为止定义我的 Node 和 CircularList 对象的代码：

class Node(object):

    def __init__(self, data = None, next_node = None):
        self.data = data
        self.next_node = next_node


class CircularLinkedList(object):

    def __init__(self, head = None, end = None):
        self.head = head
        self.end = end

    def traverse(self):

        curr_node = self.head

        while curr_node.next_node:            
            print(curr_node.data)            
            curr_node = curr_node.next_node

            if curr_node == self.head:
                break


    def insert_end(self, data):

        new_node = Node(data) 

        # handle empty list case
        if self.head == None:            
            self.head = new_node
            self.head.next_node = new_node
            self.end = new_node
            return

        # handle non-empty list case
        if self.end != None:
            self.end.next_node = new_node
            new_node.next_node = self.head        
            self.end = new_node
            return


    def insert_beg(self, data):

        new_node = Node(data)
        new_node.next_node = self.head        
        curr_node = self.head

        # handle empty list case
        if curr_node == None:            
            self.head = new_node
            self.end = new_node
            self.head.next_node = new_node
            return

        # handle non-empty list case
        if self.end != None:
            self.end.next_node = new_node
            new_node.next_node = self.head        
            self.head = new_node
            return

    def insert_mid(self, ref_node, data):

        # handle empty node case
        if ref_node == None:
            print("You've selected an empty node.")

        # if we are inserting after the end node, then just use the insert_end method
        if ref_node == self.end:
            self.insert_end(data)
            return

        # otherwise it's a true mid.
        new_node = Node(data)            
        ref_next = ref_node.next_node        
        ref_node.next_node = new_node
        new_node.next_node = ref_next


    def delete_beg(self):

        if self.head != None:            
            aft_head = self.head.next_node
            self.end.next_node = aft_head
            self.head = aft_head
        else:
            print('The list is empty, no values to delete.')

    def delete_end(self):

        if self.end != None:

            curr_node = self.head

            while curr_node.next_node.next_node != self.head:                        
                curr_node = curr_node.next_node


            self.end = curr_node
            curr_node.next_node = self.head

    def delete_mid(self, position):

        if position == 0:            
            self.delete_beg()
            return

        if position == self.list_size():
            self.delete_end()
            return


        curr_node = self.head.next_node
        count = 0

        while count <= position:            
            count = count + 1 
            curr_node = curr_node.next_node

        curr_node.next_node = curr_node.next_node.next_node


    def list_size(self):

        curr_node = self.head

        count = 0

        while curr_node.next_node:            
            count = count + 1            
            curr_node = curr_node.next_node            
            if curr_node == self.head:
                break

        return count

我在列表上尝试了不同的操作，它们似乎都工作正常，但是'我现在卡住的部分是这个部分：

def reverse(self):

    if self.head == None:
        return

    last = self.head
    prev = self.head
    curr = self.head.next_node

    while self.head != last:

        self.head = self.head.next_node
        curr.next_node = prev
        prev = curr
        curr = self.head

    curr.next_node = prev
    self.head = prev

这是我的代码的主要部分，其中插入和删除值，然后尝试反转列表：

# define a new list
circular_list = CircularLinkedList()

# insert a few values at the end
circular_list.insert_end(50)
circular_list.insert_end(60)
circular_list.insert_end(70)

# insert a few values at the beginning
circular_list.insert_beg(90)
circular_list.insert_beg(100)

# grab a node
first_node = circular_list.end

# insert value inbetween two nodes.
circular_list.insert_mid(first_node,20)

# delete the first and last value
circular_list.delete_beg()
circular_list.delete_end()

print('Before Reversal')
print('-'*20)
circular_list.traverse()

circular_list.reverse()

print('After Reversal')
print('-'*20)
circular_list.traverse()

但是当我尝试反转它时，这是输出：

Before Reversal
--------------------
90
50
60
70
After Reversal
--------------------
90
50

Answer 1

通过查看您的代码，reverse() 函数肯定存在错误。您可以很容易地看到您从未开始 while 循环迭代，因为条件在开始时为假。我会做这样的事情：

def reverse(self):

    if self.head == None:
        return

    last = self.head
    curr = self.head
    prev = self.end
    next=curr.next_node
    curr.next_node = prev
    prev = curr
    curr = next
    while curr != last:
        next=curr.next_node
        curr.next_node = prev
        prev = curr
        curr = next

如何在 Python 中反转循环链表

How to Reverse a Circular Linked List in Python

python

data-structures

circular-list