题目
单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针或引用。
请设计一个单链表，并在链表类中实现下列操作：
- get(index)：获取链表中索引 index 节点的值。如果索引无效，则返回-1。
- add_at_head(val)：在链表的第一个节点之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- add_at_tail(val)：将值为 val 的节点追加到链表的最后一个节点。
- add_at_index(index,val)：在链表中的索引 index 节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将追加到链表的末尾；如果 index 大于链表长度，则不会插入节点；如果 index 小于0，则在头部插入节点。
- delete_at_index(index)：如果索引 index 有效，则删除链表中的索引 index 的节点。
说明：链表节点的索引 index 是从 0 开始计算，比如链表中索引 1 下的节点，指的是链表中的第二个节点。
代码实现
class ListNode: # 定义单链表
def __init__(self, val=0, next=None):
self.val = val # 链表节点上存储的元素
self.next = next # 指向下一个链表节点
class MyLinkedList:
def __init__(self):
self.dummy_head = ListNode(0) # 定义虚拟头节点
self.length = 0 # 定义链表的长度
def get(self, index: int) -> int:
if 0 <= index < self.length:
cur = self.dummy_head
cur = cur.next # 因为多了一个虚拟头节点，所以需提前移动1位
while index: # 循环操作，让 cur 移动 index 位
cur = cur.next
index -= 1
return cur.val
else: # 链表节点不存在，直接返回-1
return -1
def add_at_head(self, val: int) -> None:
cur = self.dummy_head
old_head = cur.next # 临时保存原链表的头节点
cur.next = ListNode(val=val, next=old_head) # 改变节点指向，让虚拟头节点通过 next 指向新加的节点，新节点则通过 next 指向原链表的头节点
self.length += 1 # 链表长度+1
def add_at_tail(self, val: int) -> None:
cur = self.dummy_head
while cur.next is not None: # cur 不是链表最后一个节点
cur = cur.next
cur.next = ListNode(val=val, next=None) # 链表最后一个节点通过 next 指向新加的节点，新节点则通过 next 指向None
self.length += 1 # 链表长度+1
def add_at_index(self, index: int, val: int) -> None:
if 0 <= index <= self.length:
cur = self.dummy_head
while index: # 循环操作，让 cur 移动 index 位
cur = cur.next
index -= 1
if index != self.length: # 如果 index 不等于链表长度, 那么让cur通过 next 指向新加的节点，新节点则通过 next 指向cur的下个节点
post_head = cur.next
cur.next = ListNode(val=val, next=post_head)
else: # 如果 index 恰好等于链表长度，那么在链表末尾添加节点
cur.next = ListNode(val=val, next=None)
self.length += 1 # 链表长度+1
elif index < 0:
self.add_at_head(val)
def delete_at_index(self, index: int) -> None:
if 0 <= index < self.length:
cur = self.dummy_head
while index: # 循环操作，让 cur 移动 index 位
cur = cur.next
index -= 1
cur.next = cur.next.next # 删除节点
self.length -= 1 # 链表长度-1
def list_node_to_list(node): # 将单向链表转换为列表
result = []
while node:
result.append(node.val)
node = node.next
return result
测试过程
if __name__ == '__main__':
obj = MyLinkedList()
obj.add_at_head(10) # 在链表开头加新节点
obj.add_at_tail(3) # 在链表末尾加新节点
print(list_node_to_list(obj.dummy_head.next))
obj.add_at_index(1, 2) # 在链表索引1位置加新节点
print(list_node_to_list(obj.dummy_head.next))
print(obj.get(1))
obj.delete_at_index(1) # 删除链表索引1位置的节点
print(obj.get(1))
print(list_node_to_list(obj.dummy_head.next))
执行代码后，得到如下结果：
[10, 3]
[10, 2, 3]
2
3
[10, 3]
更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）
网友评论