Объяснение об указателях и манипулировании объектами в связанном списке - PullRequest
Новая
       29

Объяснение об указателях и манипулировании объектами в связанном списке

1 голос
/ 11 апреля 2020

У меня возникают проблемы с тем, чтобы обернуть голову вокруг концепции переключения указателей по сравнению с фактическим манипулированием объектами в связанном списке.

Вот код для создания связанного списка с нуля 

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

После использования этой строки в 3-й итерации голова теперь становится [1,2,3,5]

Однако, хотя эта строка не манипулирует головой, когда я прохожу список? Заголовок остается [1,2,3,4,5] после каждой итерации? 

fast = fast.next

Я прочитал это другое объяснение стека переполнения на указателях фиктивных узлов, которое было полезно, но я все еще не понимаю его.

Объяснение о фиктивных узлах и указателях в связанных списках

Заранее спасибо!

1 Ответ

1 голос
/ 11 апреля 2020

Прежде всего, приятно видеть такой понятный и легко читаемый код. Причина, по которой следующая строка не работает 

fast.next = head #fast is an object.

, заключается в том, что вы быстро объявляете объект 

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

Что происходит?

In python вы работаете с объектами, а не с указателями (а на самом деле это не указатели, это ссылки.

Иногда некоторые переданные или созданные переменные интерпретируются как объекты, а иногда как указатели (ссылки).

Хорошо, вы увидите:

Python не требует указателей для достижения этой цели, поскольку каждая переменная является ссылкой на объект. Эти ссылки немного отличаются от ссылок C ++, в том смысле, что они могут быть назначены - очень похоже на указатели в C ++. ( obmarg )

Довольно сложно сказать вам, как заставить lenaguage интерпретировать переменные как ссылки на объекты.

Если я хорошо об этом подумаю, в этом случае это можно сделать со следующей модификацией 

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

Примечание:

В этом посте обсуждается как реализовать точку

, и может дать вам больше информации о том, как с ними обращаться. *1030*

Я действительно надеюсь, что это поможет вам, спасибо за чтение этого ответа.

...