Python: как удалить ТОЛЬКО узел в односвязном списке за O (1) раз
Я прочитал сообщения ниже, но они не отвечают на мою проблему.
Этот Почта близок к объяснению. Самый популярный ответ @Rishikesh Raje гласит, что удаление последнего узла в односвязном списке является
[...] is generally not possible.
Почему это вообще невозможно, а не просто «невозможно»? Мои вопросы касаются как самой теории, так и того, как это применимо к Python? Вопрос предназначался для С.
Более того, мой другой вопрос касается случая, когда связанный список имеет только один узел, что также делает его последним узлом.
Предыстория: я решаю этот проблема на LeetCode. Хотя он не требует удаления последнего случая, я попробовал его, но, похоже, не могу получить его из-за какой-то функции, которую я не могу определить. Было бы очень полезно какое-то направление здесь. Я добавил метод вывода значений для отладки.
Вот вопрос:
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
Мой код может достичь требуемого результата 1 -> 2 -> 4:
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
nextNode = node.next
if nextNode:
node.val = nextNode.val
node.next = nextNode.next
else:
node = None
def listToString(self, head):
string = ""
while head:
string += str(head.val) + "\n"
head = head.next
return string
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
solution = Solution()
print(solution.listToString(head))
print('-'*10)
node = head.next.next
solution.deleteNode(node)
print(solution.listToString(head))
Выполнение этого дает мне:
1
2
3
4
----------
1
2
4
Но когда я меняю нижнюю часть на:
head = ListNode(1)
solution = Solution()
print(solution.listToString(head))
print('-'*10)
node = head
solution.deleteNode(head)
print(solution.listToString(head))
я получил
1
----------
1
Вопросы следующие:
Почему не печатается 1, а не None? Имейте в виду, что этот связанный список имеет только один узел (что означает, что это последний узел), и это то, что передается функции.
Это можно сделать?
Если да, то какие изменения мне следует внести?
@chrisz, я понимаю, что вы говорите. Я мог бы просто вернуть None, за исключением того, что этот метод ничего не возвращает. Он просто изменяет связанный список. Если это работает для более длинного списка, почему бы не работать с этим?
Ответы 1
Функция, которая принимает ссылку на головной узел списка, может удалить любой элемент после заголовка, но у нее нет способа удалить заголовок.
Если задуматься, это должно быть очевидно. Независимо от того, что вы делаете, ваш вызывающий по-прежнему имеет ту же ссылку на голову, которую он передал.
Но это не ограничение связанных списков как таковых, это просто ограничение вашего API. С другим API это вообще возможно:
Функция, которая принимает ссылку на объект «дескриптор списка», который содержит ссылку на головной узел, может удалить головной узел следующим образом:
handle.head = handle.head.next
Функция, которая принимает ссылку на ссылку на головной узел, например C Node **, не может быть написана непосредственно на Python, но на языках, где это возможно, это так же просто, как с дескриптором списка:
*head = (*head)->next
Дескриптор списка действительно может быть таким же простым, как:
class LinkedList:
def __init__(self, head=None):
self.head = head
Но обычно вы действительно хотите использовать его для чего-то - например, добавить к нему методы insert, delete, append и т. д., Возможно, даже сохранить длину. (Однако обратите внимание, что этот дизайн может нарушить совместное использование хвостов, когда два разных списка имеют разные заголовки, но одинаковые хвосты, потому что теперь вы можете изменить часть списка с помощью одного дескриптора LinkedList, а другой не будет знать, что вы это сделали.)
Или функция, которая принимает ссылку на головной узел и возвращает новую головку, также может удалить головку:
return head.next
Давайте разберемся с этим более подробно:
def deleteNode(head, node):
if head == node:
return None
ptr = head
while ptr and ptr.next != node:
ptr = ptr.next
if ptr.next == node:
ptr.next = node.next
return head
Требуется небольшая обработка ошибок, но если вы следуете правилам, это работает:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
# This goes from 1->2->3->4 to 1->2->4
head = deleteNode(head, head.next.next)
# And this goes to 2->4
head = deleteNode(head, head)
И, очевидно, если вы измените это, чтобы искать значение вместо узла, то же самое сработает.
Если бы я мог, я бы добавил больше пунктов, заявив, что это ограничение не связанных списков как таковых, а ограничения реализации.
Стоимость достигать узла в связанном списке составляет O (n), стоимость самого удаления составляет O (1), поэтому, если вам уже предоставлен узел (который, как вы говорите, есть), вы можете сделать это в постоянное время. .