0707. Design Linked List¶
题目信息¶
- 题号:
0707
- 难度:
Medium
- 主题:
设计、链表、零基下标
- 原题:
- 重点:
链表状态跨调用保留;索引从零开始,越界查询返回
-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。