Leetcode 707 设计链表，我的删除函数在索引0处删除时有问题吗？

Question

我目前陷入 Leetcode 707：设计一个链表，我想我已经完成了大部分任务，但我只通过了 62/65 个测试用例。当我尝试从索引 0 中删除时，问题似乎出在 deleteAtIndex 函数上。我使用的是 2 个虚拟双向链表方法。我认为我的逻辑是正确的，因为如果索引已经是0，它应该跳过while循环并简单地删除第一个节点，对吗？除了我尝试自己测试它并且由于某种原因它不起作用，也许我错过了一些简单的东西？任何帮助都会很棒，谢谢！

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class MyLinkedList:

    def __init__(self):
        self.left = ListNode(0)
        self.right = ListNode(0)
        self.left.next = self.right
        self.right.prev = self.left

    def get(self, index: int) -> int:
        cur = self.left.next
        while index > 0 and cur != None:
            index -= 1
            cur = cur.next

        if cur != None and cur != self.right and index == 0:
            return cur.val
        else:
            return -1

    def addAtHead(self, val: int) -> None:
        new_node = ListNode(val)
        after_head = self.left.next
        after_head.prev = new_node
        new_node.next = after_head
        self.left.next = new_node
        new_node.prev = self

    def addAtTail(self, val: int) -> None:
        new_node = ListNode(val)
        before_end = self.right.prev
        before_end.next = new_node
        new_node.prev = before_end
        self.right.prev = new_node
        new_node.next = self.right

    def addAtIndex(self, index: int, val: int) -> None:
        new_node = ListNode(val)

        cur = self.left.next
        while index > 0 and cur != None:
            index -= 1
            cur = cur.next

        if cur == None:
            return
        
        if cur.val == 0 and cur.next == None:
            before_end = self.right.prev
            before_end.next = new_node
            new_node.prev = before_end
            self.right.prev = new_node
            new_node.next = self.right
        elif cur.val == 0 and cur.prev == None:
            after_head = self.left.next
            after_head.prev = new_node
            new_node.next = after_head
            self.left.next = new_node
            new_node.prev = self
        else:
            cur.prev.next = new_node
            new_node.prev = cur.prev
            cur.prev = new_node
            new_node.next = cur

    def deleteAtIndex(self, index: int) -> None:
        cur = self.left.next

        while index > 0 and cur != None:
            index -= 1
            cur = cur.next
        
        if cur != None and cur != self.right and index == 0:
            cur.prev.next = cur.next
            cur.next.prev = cur.prev

Answer 1

• 调试代码很困难。

• 你可以添加更多的功能，这样调试起来会更容易：

• 您可以分离

  add

  和

  remove

  方法。

• 您可以使用 include

  forward

  和

  backward

  遍历。

• 那么，

  deleteAtIndex

  就容易写了：

    def deleteAtIndex(self, index):
        if 0 <= index <= self.size // 2:
            self.remove(self.forward(0, index, self.head.next))
        elif self.size // 2 < index < self.size:
            self.remove(self.backward(self.size - 1, index, self.tail.prev))

代码

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None


class MyLinkedList:
    def __init__(self):
        self.head = self.tail = Node(-1)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add(self, prev, val):
        node = Node(val)
        node.prev = prev
        node.next = prev.next
        node.prev.next = node.next.prev = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def forward(self, start, end, curr):
        while start != end:
            start += 1
            curr = curr.next
        return curr

    def backward(self, start, end, curr):
        while start != end:
            start -= 1
            curr = curr.prev
        return curr

    def get(self, index):
        if 0 <= index <= self.size:
            return self.forward(0, index, self.head.next).val
        elif self.size // 2 < index < self.size:
            return self.backward(self.size - 1, index, self.tail.prev).val
        return -1

    def addAtHead(self, val):
        self.add(self.head, val)

    def addAtTail(self, val):
        self.add(self.tail.prev, val)

    def addAtIndex(self, index, val):
        if 0 <= index <= self.size // 2:
            self.add(self.forward(0, index, self.head.next).prev, val)
        elif self.size // 2 < index <= self.size:
            self.add(self.backward(self.size, index, self.tail).prev, val)

    def deleteAtIndex(self, index):
        if 0 <= index <= self.size // 2:
            self.remove(self.forward(0, index, self.head.next))
        elif self.size // 2 < index < self.size:
            self.remove(self.backward(self.size - 1, index, self.tail.prev))