如何返回链表的中间节点

Question

在检查链表的中间节点时，我对链表中的 while 循环条件如何工作感到困惑这是我找到链表中间节点的正确代码class Node(object):    def __init__(self, data):        self.data = data        self.next = Noneclass linkedList(object):    def __init__(self):        self.head = None    def append(self, data):        node = Node(data)        if self.head == None:            self.head = node        temp = self.head        while temp.next:            temp = temp.next        temp.next = node    def middle(self):        first = self.head        second = self.head        while second and second.next:            second = second.next.next            first = first.next        print(first.data)如果我将 while 循环更改为while second:或者while second.next:我收到一条错误消息AttributeError: 'NoneType' object has no attribute 'next' on line 24我只是想知道为什么它是重要的是有两个second和second.next

Answer 1

对于初学者，您的 append 方法不起作用，并且会陷入无限的 while 循环，因为您在添加第一个元素时不会退出 append。正确的版本是

def append(self, data):

    node = Node(data)

    if self.head == None:

        self.head = node

        return

    else:

        temp = self.head

        while temp.next:

            temp = temp.next

        temp.next = node

至于您的另一个问题，我们希望找到偶数和奇数列表的循环中间，second.next覆盖奇数列表情况和second覆盖偶数列表情况，因为第二个指针将指向空值，或者它将本身为 null ，如果你只使用其中一个，你会得到你描述的错误，因此你需要在 while 循环中同时拥有这两个条件

Answer 2

该解决方案通过使用两个指针来工作。第一个每次走 1 步，第二步一次走 2 步。但是，在采取 2 个步骤时，需要验证两件事：

1. 有一个有效的下一步

2. 在上面提到的下一步之后有一个步骤

如果您跳过一个检查，它将进入循环，但在边界条件下它找不到下一个。举例说明：如果有 4 个节点并且您只second.next在第 3 个节点处检查，那么您将拥有second.next有效并且您将进入while循环但在其中您可以直接访问second.next.next

F,S | 1 --> 2 --> 3 --> 4 --> 无