如何删除链表中的节点

Question

我正在使用Python实现链表。这是我的代码

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
class LinkedList:
    def __init__(self, head = None):
        self.head = head
    def append(self, newElement):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = newElement
        else:
            self.head = newElement
    #get position time complexity O(n)
    #get the node at a specific position
    def get_position(self, position):
        current = self.head
        current_pos = 1
        while current_pos <= position:
            if current_pos == position:
                return current
            current = current.next
            current_pos += 1
        return None
    #Insert element
    # Time complexity O(n)
    def insert_element(self, element, position):
        if position > 1:
            front_pos = self.get_position(position - 1)
            end_pos = self.get_position(position + 1)
            front_pos.next = element
            element.next = end_pos
        else:
            element.next = self.head
            self.head = element
    def delete_element(self, element):
        current = self.head
        previous = None
        while current:
            if current.value == element:
                if not previous:
                    self.head = element
                previous.next = current.next
            else:
                current = current.next
                previous = current
        else:
            return False

node1 = Node("Iron Man")
node2 = Node("Capitain America")
node3 = Node("Doctor Strange")
node4 = Node("Spider man")
node5 = Node("Rieder")
print("Node1 Value is {}".format(node1.value))
print("Node1 next Value is {}".format(node1.next))
print("Node2 Value is {}".format(node2.value))
print("Node2 next Value is {}".format(node2.next))
Avengers = LinkedList()
Avengers.append(node1)
print("Firt element in link list is {}".format(Avengers.head.value))
Avengers.append(node2)
print("After Iron Man is {}".format(Avengers.head.next.value))
print(Avengers.get_position(2).value)
Avengers.append(node3)
Avengers.append(node4)
Avengers.insert_element(node5, 4)
print(Avengers.get_position(4).value)
Avengers.delete_element(node5)
print(Avengers.get_position(4).value)

这是我的输出：

Node1 Value is Iron Man
Node1 next Value is None
Node2 Value is Capitain America
Node2 next Value is None
Firt element in link list is Iron Man
After Iron Man is Capitain America
Capitain America
Rieder
Rieder

列表结构链接如下：钢铁侠 -> 美国首都 -> 奇异博士 -> 里德 -> 蜘蛛侠

因此，如果我不想要"Rieder"节点。输出的最后一行应显示"蜘蛛侠">

我的代码中发生了什么？非常感谢帮助我的人:D

Answer 1

一个问题是您似乎更新了current，然后使用新的 current 值更新previous。 我会回到你的delete方法，一行一行地看一遍。 如果你在纸上写出列表在每一行的状态，看看你是否可以纠正算法，这会有所帮助。

else:
    current = current.next
    previous = current

Answer 2

首先，您需要修复insert_element函数。您插入的节点不正确。这是正确的方法

def insert_element(self, element, position):
        if position > 1:
            front_pos = self.get_position(position - 1)
            # end_pos should not be position + 1, because it will
            # skip the element at index=position
            end_pos = self.get_position(position)
            front_pos.next = element
            element.next = end_pos
        else:
            element.next = self.head
            self.head = element

接下来，删除元素时，您只需传递节点的值，而不是节点本身。我对您的代码进行了一些小的更改以修复一些错误。查看评论以获取更多信息

def delete_element(self, element):
        current = self.head
        previous = None
        while current:
            if current.value == element:
                # This means that the head itself
                # has to be deleted
                if not previous:
                    self.head = self.head.next
                # Add an else block correctly here
                # in case head is not to be deleted
                else:
                    previous.next = current.next
                # break the loop when the element is deleted
                break
            else:
                # First copy the current into previous,
                # Then change the value of current
                previous = current
                current = current.next

此外，在删除功能结束时也不需要else: return False块。