当前位置：首页 > news >正文

二、链表（1）

news 2025/7/2 8:51:06

203.移除链表元素
创建一个虚拟哨兵头节点，就不用考虑原本头结点要不要删除

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:cur = dum = ListNode(next = head)while cur.next:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dum.next

707.设计链表

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):# 初始化虚拟头节点和节点个数self.dum = ListNode()self.cnt = 0def get(self, index: int) -> int:if index < 0 or index >= self.cnt:return -1cur = self.dum.nextfor _ in range(index):cur = cur.nextreturn cur.valdef addAtHead(self, val: int) -> None:self.addAtIndex(0,val)def addAtTail(self, val: int) -> None:self.addAtIndex(self.cnt, val)def addAtIndex(self, index: int, val: int) -> None:if index > self.cnt:returnpre = self.dumfor _ in range(index):  # 这里包含了add head和tail所以前面可以直接用addindexpre = pre.nextpre.next = ListNode(val = val, next = pre.next)self.cnt += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.cnt:returnelse:pre = self.dumfor _ in range(index):pre = pre.nextpre.next = pre.next.nextself.cnt -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

# （版本二）双链表法
class ListNode:def __init__(self, val=0, prev=None, next=None):self.val = valself.prev = prevself.next = nextclass MyLinkedList:def __init__(self):self.head = Noneself.tail = Noneself.size = 0def get(self, index: int) -> int:if index < 0 or index >= self.size:return -1if index < self.size // 2:current = self.headfor i in range(index):current = current.nextelse:current = self.tailfor i in range(self.size - index - 1):current = current.prevreturn current.valdef addAtHead(self, val: int) -> None:new_node = ListNode(val, None, self.head)if self.head:self.head.prev = new_nodeelse:self.tail = new_nodeself.head = new_nodeself.size += 1def addAtTail(self, val: int) -> None:new_node = ListNode(val, self.tail, None)if self.tail:self.tail.next = new_nodeelse:self.head = new_nodeself.tail = new_nodeself.size += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returnif index == 0:self.addAtHead(val)elif index == self.size:self.addAtTail(val)else:if index < self.size // 2:current = self.headfor i in range(index - 1):current = current.nextelse:current = self.tailfor i in range(self.size - index):current = current.prevnew_node = ListNode(val, current, current.next)current.next.prev = new_nodecurrent.next = new_nodeself.size += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:returnif index == 0:self.head = self.head.nextif self.head:self.head.prev = Noneelse:self.tail = Noneelif index == self.size - 1:self.tail = self.tail.previf self.tail:self.tail.next = Noneelse:self.head = Noneelse:if index < self.size // 2:current = self.headfor i in range(index):current = current.nextelse:current = self.tailfor i in range(self.size - index - 1):current = current.prevcurrent.prev.next = current.nextcurrent.next.prev = current.prevself.size -= 1

206.反转链表
需要3个变量，除了pre cur还有nxt保存当前的下一个（不然当前翻转完找不到下一个了）
得判断是否null才能next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre = Nonecur = head#while cur:nxt = cur.next  # cur有可能是空，所以nxt不能放在外面，null是没有next的，所以得判断是否null才能nextcur.next = prepre = curcur = nxtreturn pre