707. Design Linked List

https://leetcode.com/problems/design-linked-list/

solution

• 增加节点和删除节点的有效index范围不同

class MyLinkedList:
    def __init__(self):
        self.dummy = ListNode()
        self.size = 0

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

        cur = self.dummy.next
        for i in range(index):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        tmp = self.dummy.next
        self.dummy.next = ListNode(val)
        self.dummy.next.next = tmp
        self.size += 1

    def addAtTail(self, val: int) -> None:
        cur = self.dummy
        while cur.next is not None:
            cur = cur.next
        cur.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return

        cur = self.dummy
        for i in range(index):
            cur = cur.next

        tmp = cur.next
        cur.next = ListNode(val)
        cur.next.next = tmp

        self.size += 1

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

        i = 0
        cur = self.dummy
        while i < index:
            cur = cur.next
            i += 1

        cur.next = cur.next.next
        self.size -= 1


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

时间复杂度：index相关操作为 O(index), 其余为 O(1) 空间复杂度：O(n)

Follow up

432. All O`one Data Structure