0707. Design Linked List ======================================================================================================================== 题目信息 -------- :题号: 0707 :难度: Medium :主题: 设计、链表、零基下标 :原题: `LeetCode 0707 `_ :重点: 链表状态跨调用保留;索引从零开始,越界查询返回 ``-1``,按索引插入和删除需要区分等于长度与大于长度的情况 题目重述 -------- 实现 ``MyLinkedList`` 类,不得直接使用语言提供的内置链表库。新建对象时链表为空,所有节点按零基下标编号,并支持以下操作: * ``get(index)``:若 ``index`` 是有效下标,返回对应节点的值;否则返回 ``-1``; * ``addAtHead(val)``:在当前首节点之前插入值为 ``val`` 的节点,使它成为新的首节点; * ``addAtTail(val)``:在链表末尾追加值为 ``val`` 的节点; * ``addAtIndex(index, val)``:在当前下标 ``index`` 的节点之前插入新节点。若 ``index`` 等于链表长度,则追加到末尾;若 ``index`` 大于链表长度,则不插入; * ``deleteAtIndex(index)``:当 ``index`` 有效时删除对应节点;无效时不改变链表。 同一个对象必须在多次调用之间保留链表状态。``index`` 和 ``val`` 均在 ``[0, 1000]`` 范围内,上述方法的调用总数最多为 ``2000``。 自建示例 -------- 覆盖头插、尾插、按下标插入和越界操作: .. code-block:: text 输入: 操作 = ["MyLinkedList", "addAtTail", "addAtHead", "addAtIndex", "addAtIndex", "get", "deleteAtIndex", "get"] 参数 = [[], [5], [2], [2,9], [5,7], [2], [0], [0]] 输出:[null, null, null, null, null, 9, null, 5] 解释:链表依次变为 [5]、[2,5]、[2,5,9];下标 5 大于当前长度 3,因此 7 不会插入。下标 2 的值为 9,删除首节点后链表为 [5,9],此时下标 0 的值为 5。 空链表上的无效访问: .. code-block:: text 输入: 操作 = ["MyLinkedList", "get", "deleteAtIndex", "addAtIndex", "get"] 参数 = [[], [0], [0], [0,6], [0]] 输出:[null, -1, null, null, 6] 解释:空链表没有下标 0;删除无效下标不改变状态。长度为 0 时在下标 0 插入等同于尾部追加,之后可取得值 6。