链表

力扣

用双向链表和伪头、伪尾能提升性能和简化代码

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


class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head, self.tail = ListNode(0), ListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        if index + 1 < self.size - index:
            curr = self.head
            for _ in range(index + 1):
                curr = curr.next
        else:
            curr = self.tail
            for _ in range(self.size - index):
                curr = curr.prev

        return curr.val

    def addAtHead(self, val: int) -> None:
        pred, succ = self.head, self.head.next

        node = ListNode(val)
        node.prev = pred
        node.next = succ
        pred.next = node
        succ.prev = node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        succ, pred = self.tail, self.tail.prev

        node = ListNode(val)
        node.prev = pred
        node.next = succ
        pred.next = node
        succ.prev = node
        self.size += 1

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

        if index > self.size:
            return

        if index < 0:
            index = 0

        if index < self.size - index:
            pred = self.head
            for _ in range(index):
                pred = pred.next
            succ = pred.next
        else:
            succ = self.tail
            for _ in range(self.size - index):
                succ = succ.prev
            pred = succ.prev

        node = ListNode(val)
        node.prev = pred
        node.next = succ
        pred.next = node
        succ.prev = node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:

        if index < 0 or index >= self.size:
            return

        if index < self.size - index:
            pred = self.head
            for _ in range(index):
                pred = pred.next
            succ = pred.next.next
        else:
            succ = self.tail
            for _ in range(self.size - index - 1):
                succ = succ.prev
            pred = succ.prev.prev

        pred.next = succ
        succ.prev = pred
        self.size -= 1