Изменить узел связанного списка "на месте" в Python - PullRequest
Новая
       22

Изменить узел связанного списка "на месте" в Python

1 голос
/ 07 июля 2019

Я столкнулся с моим вопросом, когда практиковал (по общему признанию, простую) проблему LeetCode.Однако мой настоящий вопрос касается Python, а не ответа на саму проблему.Вы увидите полное описание проблемы ниже, после чего я объясню свой подход, сопоставлю его с фактическим решением, а затем (наконец) задам мой вопрос.

LeetCode Problem: Удалить узелв связанном списке

Проблема:

Написать функцию для удаления узла (кроме хвоста) в односвязном списке, предоставляя только доступ к этому узлу.

Данный связанный список - head = [4,5,1,9], который выглядит следующим образом:

img

Пример 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Пример 2: 

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Примечание:

  • Связанный списокбудет иметь как минимум два элемента.
  • Все значения узлов будут уникальными.
  • Данный узел не будет хвостом и всегда будет действительным узлом связанного списка.
  • Не возвращайте ничего из вашей функции.

Мой подход:

Я дал быстрый ответ (который был субоптимальным при O (n), но это не такточка), где я переназначаю значения удаленного узла и всех узлов вправо, сдвигая их все на одну единицу влево.В этом примере узел в скобках будет переназначен следующим образом:

  1. 4->[5]->1->9->None становится
  2. 4->1->[1]->9->None, затем
  3. 4->1->9->[9]->None и, наконец,
  4. 4->1->9->None.

Или, по крайней мере, это то, что я ожидал от кода, который я написал ниже. 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        while node != None:
            node = node.next

меня удивил этот ответ, чтовходной связанный список был точно таким же, как выходной связанный список.Вот снимок экрана с выводом:

LeetCode Output for incorrect deleteNode function

Фактическое решение:

решение ,со сложностью O (1), показано ниже с соответствующим (правильным) выводом. 

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

LeetCode Output for correct deleteNode function

Мой вопрос:

Почему node.val = node.next.val и node.next = node.next.next модифицируют узел связанного списка "на месте", а переназначение node в node = node.next не влияет на ссылки на объект node?

1 Ответ

4 голосов
/ 07 июля 2019

node = node.next просто переназначает параметр deleteNode, который не влияет ни на что, кроме функции.

Подумайте об этом так: вы ожидаете, что это изменит x? 

x = 1

def f(a):
    a = 2

f(x)

Не будет.a вот только локальная ссылка внутри f.Все, что он переназначает, это изменяет объект, на который указывает a.

Сравните это с: 

x = []

def f(a):
    a.append(2)

f(x)

Это изменит x.Здесь вы не переназначаете локальную ссылку, вы изменяете объект, на который указывает локальная ссылка .С вашим вторым кодом node.val = node.next.val изменяет поле внутри node.Это меняет объект.

В этом разница между вашими двумя частями кода.Первый фрагмент кода просто изменяет ссылку на объект.Второй фрагмент кода изменяет сам объект.

...