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。

自建示例

覆盖头插、尾插、按下标插入和越界操作:

输入:
操作 = ["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。

空链表上的无效访问:

输入:
操作 = ["MyLinkedList", "get", "deleteAtIndex", "addAtIndex", "get"]
参数 = [[], [0], [0], [0,6], [0]]
输出:[null, -1, null, null, 6]
解释:空链表没有下标 0;删除无效下标不改变状态。长度为 0 时在下标 0 插入等同于尾部追加,之后可取得值 6。