关于指针与操作链表中对象的说明

Question

我很难理解切换指针与实际操作链表中的对象的概念

下面是从头开始构建链表的代码

class ListNode:

    def __init__(self, val:int, nextNode=None):
        self.val = val
        self.next = nextNode

class LinkedList:

    def __init__(self, val=None):

        self.head = None
        self.tail = None

    def addValue(self, val:int):
        if self.head == None:
            self.head = self.tail = ListNode(val)

        else:
            self.tail.next = ListNode(val)
            self.tail = self.tail.next
        return self.tail

    def addMultiple(self, values:list):

        for i in values:
            self.addValue(i)


    def add_to_beginning(self, val):
        if self.head == None:
            self.head = self.tail = ListNode(val)
        else:
            self.head = ListNode(val, self.head)

    def display(self):

        elems = []

        curr = self.head
        while curr:
            elems.append(curr.val)
            curr = curr.next

        print(elems)

在此处创建链接列表：

l1 = LinkedList()
l1.addMultiple([1,2,3,4,5])

例如，如果我想将第n个元素移动到头部，那么我创建了这个函数

class Solution:

    def move_n_to_head(self, head, n):

        if head == None:
            return None
        if head.next == None:
            return head

        temp = None
        count = 0
        dummy = fast = slow = ListNode(0)

        fast.next = head
        while fast:

            if count == n:
                temp = fast.next
                fast.next = fast.next.next #why does this line manipuate the head?
                break

            fast = fast.next #why does this line NOT manipulate the head?
            count += 1

        slow.next = temp
        slow.next.next = head
        return dummy.next

一切正常，我得到了我想要的解决方案，但具体来说，我不明白为什么这条线操纵头部

fast.next = fast.next.next

在第三次迭代中使用上述行后，头部现在变为[1,2,3,5]

然而，当我在列表中穿行时，这一行不会操纵头部？每次迭代后，头部仍然保持[1,2,3,4,5]

fast = fast.next

我读了另一篇关于伪节点指针的stackoverflow解释，这很有帮助，但我仍然不理解

Explanation about dummy nodes and pointers in linked lists

提前谢谢

Answer 1

首先，很高兴看到这样一个清晰易读的代码。下面这行行不通的原因是什么

fast.next = head #fast is an object.

是因为您将fast声明为对象

dummy = fast = slow = ListNode(0) #just here

发生了什么事？

在python中，您使用的是对象而不是指针（指针实际上不是对象，而是引用）

有时传递或创建的一些变量被解释为对象，有时被解释为指针（引用）

那么你会看到,

Python doesn't need pointers in order to achieve this as every variable is a reference to an object. These references are slightly different from C++ references, in that they can be assigned to - much like pointers in C++. (obmarg)

很难告诉您如何让Lenagage将变量解释为对象引用

如果我想得好的话，在这种情况下可以做如下修改

class Solution:

    def move_n_to_head(self, head, n):

        if head == None:
            return None
        if head.next == None:
            return head

        temp = None
        count = 0
        dummy = slow = ListNode(0)

        fast = head #fast now "points" to head 
        # (it depends if it is taken as a copy of head or a reference to it)
        while fast:

            if count == n:
                temp = fast.next
                fast.next = fast.next.next #It should be solved
                break

            fast = fast.next
            count += 1

        slow.next = temp
        slow.next.next = head
        return dummy.next

注：

This post讨论如何在python中实现指针，并可能为您提供有关如何处理指针的更多信息

我真的希望它能帮助你，谢谢你阅读这个答案