1.題目描述：

設(shè)計(jì)鏈表的實(shí)現(xiàn)誉券。您可以選擇使用單鏈表或雙鏈表击吱。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next虑椎。val 是當(dāng)前節(jié)點(diǎn)的值榆鼠，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用纲爸。如果要使用雙向鏈表，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)妆够。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的识啦。

在鏈表類(lèi)中實(shí)現(xiàn)這些功能：

get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無(wú)效责静，則返回-1袁滥。
addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)。插入后灾螃，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素揩徊。
addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)腰鬼。如果 index 等于鏈表的長(zhǎng)度，則該節(jié)點(diǎn)將附加到鏈表的末尾塑荒。如果 index 大于鏈表長(zhǎng)度熄赡，則不會(huì)插入節(jié)點(diǎn)。如果index小于0齿税，則在頭部插入節(jié)點(diǎn)彼硫。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)凌箕。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //鏈表變?yōu)?-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //現(xiàn)在鏈表是1-> 3
linkedList.get(1); //返回3

提示：

所有val值都在 [1, 1000] 之內(nèi)拧篮。
操作次數(shù)將在 [1, 1000] 之內(nèi)。
請(qǐng)不要使用內(nèi)置的 LinkedList 庫(kù)牵舱。

2.分析

設(shè)計(jì)鏈表串绩，因?yàn)檫@里有非常多的關(guān)于鏈表長(zhǎng)度的判斷，所以關(guān)鍵點(diǎn)在于我們的鏈表需要保存一個(gè)鏈表的長(zhǎng)度芜壁，避免每次刪除或者讀鏈表時(shí)不必要的長(zhǎng)度判斷礁凡。

3.解決

#
# @lc app=leetcode.cn id=707 lang=python3
#
# [707] 設(shè)計(jì)鏈表
#

# @lc code=start
class MyLinkedList:
    """
    這道題目的關(guān)鍵在于，可以通過(guò)size屬性來(lái)獲取本鏈表的長(zhǎng)度慧妄，避免在一些刪除和添加操作時(shí)顷牌，還需要去遍歷整個(gè)鏈
    表看是否符合要求
    """

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dummy_head = ListNode(0)
        self.size = 0

    def get(self, index: int) -> int:
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        """
        # todo 易錯(cuò)點(diǎn)，index = self.size也是非法的index
        if index < 0 or index >= self.size:
            return -1

        cur_node = self.dummy_head
        for _ in range(index+1):
            cur_node = cur_node.next
        
        return cur_node.val

    def addAtHead(self, val: int) -> None:
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        """
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        """
        if index > self.size:
            return
        
        if index < 0:
            index = 0
        
        pre_node = self.dummy_head

        for _ in range(index):
            pre_node = pre_node.next
        
        self.size += 1
        
        tmp_node = ListNode(val)
        tmp_node.next = pre_node.next
        pre_node.next = tmp_node

    def deleteAtIndex(self, index: int) -> None:
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        # todo index = self.size也是非法的
        if index < 0 or index >= self.size:
            return

        pre_node = self.dummy_head

        for _ in range(index):
            pre_node = pre_node.next
        
        pre_node.next = pre_node.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)
# @lc code=end