题目
Leetcode707. 设计链表
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
- MyLinkedList() 初始化 MyLinkedList 对象。
- int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
- void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
- void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
- void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。 - void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
题解
class MyLinkedList:
def __init__(self):
self.val = None
self.next = None
self._length = 0 # 用于记录链表长度，用于移除、插入时检查前置条件
self._last = self # 记录末尾节点节点，用于快速尾插
def get(self, index: int) -> int:
"""
获取第index个节点的值
"""
if index >= self._length:
return -1
res = self
for _ in range(index + 1):
res = res.next
return res.val
def addAtHead(self, val: int) -> None:
"""
将值为val的节点插入链表表首
[由于需要插入表首，self为虚拟节点，指向当前表首]
"""
tmp = MyLinkedList()
tmp.val, tmp.next = val, self.next
self.next = tmp
if self._length == 0:
self._last = tmp # 只有一个元素，将插入的节点标记为 _last
self._length += 1 # 更新链表长度
def addAtTail(self, val: int) -> None:
"""尾插"""
tmp = MyLinkedList()
tmp.val = val
# 将节点插入链表尾端，并更新 _last
self._last.next = tmp
self._last = tmp
self._length += 1 # 更新链表长度
def addAtIndex(self, index: int, val: int) -> None:
"""
在指定位置插入节点
"""
# 插入节点索引超过链表长度
if index > self._length:
return
if index == 0:
# 首插
self.addAtHead(val)
elif index == self._length:
# 尾插
self.addAtTail(val)
else:
# 插入中间节点
tmp = self
for _ in range(index):
tmp = tmp.next
tmp.addAtHead(val)
self._length += 1 # 更新链表长度
def deleteAtIndex(self, index: int) -> None:
"""
删除指定位置节点
"""
# 插入节点索引超过链表长度
if index >= self._length:
return
elif index == 0:
# 删除首节点
self.next = self.next.next
else:
tmp = self
for _ in range(index):
tmp = tmp.next
tmp.next = tmp.next.next
if index == self._length - 1:
self._last = tmp
self._length -= 1 # 更新链表长度
def print_list(self):
"""
打印当前链表节点，用于测试，如下所示：
index 1 2 3 ...
value 11 2 33 ...
"""
tmp = self.next
idx = 0
index_str = ''
val_str = ''
while tmp:
interval = len(str(tmp.val)) - len(str(idx))
index_str = index_str + str(idx) + ' ' * (1 if interval == 0 else 1 + interval if interval > 0 else 1)
val_str = val_str + str(tmp.val) + ' ' * (1 if interval == 0 else 1 + abs(interval) if interval < 0 else 1)
tmp = tmp.next
idx += 1
print(index_str)
print(val_str)
def test_run(self, exc_str_list: list, val_list: list):
"""
测试，用于直接输入 LeetCode 测试数据进行测试
说明：测试数据第一步为新建实例，需手动新建实例并删去对应值（如下所示），再调用
"""
for i in range(len(val_list)):
print(exc_str_list[i], val_list[i])
getattr(self, exc_str_list[i])(*val_list[i])
self.print_list()
if exc_str_list[i] == 'get':
print(f'get({val_list[i][0]}) = ', getattr(self, exc_str_list[i])(*val_list[i]))
print('length = ', self._length)
print('==============================================')
if __name__ == '__main__':
MyLinkedList().test_run(
["addAtHead", "addAtIndex", "addAtIndex", "addAtHead", "deleteAtIndex", "addAtIndex", "addAtHead",
"addAtTail", "addAtHead", "get", "addAtTail", "addAtTail", "addAtIndex", "addAtTail", "addAtTail",
"addAtHead", "addAtTail", "addAtHead", "addAtTail", "addAtHead", "addAtTail", "addAtTail", "addAtHead",
"addAtTail", "addAtIndex", "addAtHead", "deleteAtIndex", "addAtHead", "addAtHead", "addAtHead",
"addAtHead", "addAtIndex", "addAtHead", "addAtTail", "addAtHead", "deleteAtIndex", "addAtTail",
"deleteAtIndex", "addAtTail", "addAtTail", "addAtTail", "addAtTail", "addAtHead", "addAtTail",
"get", "addAtIndex", "get", "deleteAtIndex", "addAtTail", "addAtHead", "addAtTail", "addAtTail",
"addAtIndex", "addAtHead", "addAtHead", "addAtHead", "addAtHead", "addAtHead", "addAtTail", "deleteAtIndex",
"deleteAtIndex", "addAtHead", "addAtHead", "addAtTail", "addAtHead", "get", "addAtIndex", "addAtIndex", "get",
"addAtTail", "get", "addAtTail", "deleteAtIndex", "get", "addAtTail", "addAtTail", "addAtHead", "addAtTail",
"deleteAtIndex", "addAtHead", "addAtHead", "addAtHead", "deleteAtIndex", "addAtTail", "addAtIndex", "addAtTail",
"addAtTail", "addAtIndex", "addAtIndex", "addAtHead", "addAtIndex", "addAtHead", "addAtHead", "addAtTail",
"addAtIndex", "addAtTail", "get", "addAtHead", "addAtTail", "addAtHead", "addAtHead"],
[[86], [1, 54], [1, 14], [83], [4], [3, 18], [46], [3], [76], [5], [79], [74], [7, 28], [68],
[16], [82], [24], [30], [96], [21], [79], [66], [2], [2], [7, 57], [59], [21], [19], [55], [46],
[17], [16, 41], [97], [85], [63], [30], [11], [16], [91], [29], [47], [20], [12], [80], [15], [12, 8],
[21], [30], [11], [54], [51], [41], [8, 88], [62], [7], [59], [73], [73], [55], [9], [7], [49], [99],
[17], [44], [11], [26, 86], [10, 99], [19], [71], [29], [32], [2], [3], [16], [2], [83], [31], [3], [23],
[64], [96], [27], [81], [12, 78], [21], [69], [5, 35], [8, 72], [60], [19, 73], [55], [83], [86], [31, 70],
[49], [19], [64], [22], [25], [13]]
)
