Python全系列 教程
3567个小节阅读:5930.6k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
一种更复杂的链表是“双向链表”或“双面链表”
每个节点有两个连接:一个指向前一个节点,(当此“连接”为第一个“连接”时,指向空值或者空列表);而另一个指向下一个节点,(当此“连接”为最后一个“连接”时,指向空值或者空列表)
xxxxxxxxxx
def __init__(self): #初始化双链表
def get(self, index: int) -> int: #获取双链表中第index个节点的值
def addAtHead(self, val: int) -> None: #在双链表的第一个元素之前添加一个值为val的节点。
def addAtTail(self, val: int) -> None: #将值为val的节点追加到链表的最后一个元素。
def addAtIndex(self, index: int, val: int) -> None: #在链表中的第index个节点之前添加值为val的节点。如果index等于链表的长度,则该节点将附加到链表的末尾。如果index大于链表长度,则不会插入节点,如果index小于0,则在头部插入节点。
def deleteAtIndex(self, index: int) -> None: #如果索引index有效,则删除链表中的第index个节点。
def getNode(self, index: int) -> node: #获取节点
def addNode(self, first: node, second: node, val: int) -> None: #添加节点
xxxxxxxxxx
class node:
def __init__(self, val):
self.val = val
self.pre = None #指向前面节点的指针
self.next = None #指向后面节点的指针
xxxxxxxxxx
class MyLinkedList:
def __init__(self):
self.head = node(-1) #虚拟头节点
self.tail = node(-1) #虚拟尾节点
self.head.next = self.tail # 让虚拟头节点指向虚拟尾节点
self.tail.pre = self.head #虚拟尾节点指回虚拟头节点
self.size = 0
获取双链表中第index个节点
xxxxxxxxxx
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
curr = self.getNode(index)
return curr.val
我们来下如何来写这个getNode方法,我们需要在方法中反复使用
xxxxxxxxxx
def getNode(self, index: int) -> node:
if index < self.size // 2:
curr = self.head
for i in range(index + 1):
curr = curr.next
else:
curr = self.tail
for i in range(self.size - index):
curr = curr.pre
return curr
编写addNode函数
xxxxxxxxxx
def addNode(self, first: node, second: node, val: int) -> None:
temp_node = node(val)
temp_node.next = second
second.pre = temp_node
first.next = temp_node
temp_node.pre = first
self.size += 1
在单链表的第一个元素之前添加一个值为val的节点
xxxxxxxxxx
def addAtHead(self, val: int) -> None:
self.addNode(self.head, self.head.next, val)
将值为val的节点追加到链表的最后一个元素
xxxxxxxxxx
def addAtTail(self, val: int) -> None:
self.addNode(self.tail.pre, self.tail, val)
在链表中的第index个节点之前添加值为val的节点。
xxxxxxxxxx
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size:
return
if index < 0:
index = 0
node = self.getNode(index)
self.addNode(node.pre, node, val)
如果索引index有效,则删除链表中的第index个节点
xxxxxxxxxx
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
p = self.getNode(index)
p.pre.next = p.next
p.next.pre = p.pre
self.size -= 1