网站如何做excel预览,电脑网页打不开但是可以上网,上海教育网站官网,个人做淘宝客网站好做吗对于链表完全陌生#xff0c;但是看题目又觉得和数组一样的 链表理论基础 Q#xff1a;什么是链表#xff1f; A#xff1a;链表是由一系列结点组成的。每一个结点由两部分组成#xff1a;数据和指针。 203.移除链表元素 题目#xff1a; 给你一个链表的头节点 head 和…对于链表完全陌生但是看题目又觉得和数组一样的 链表理论基础 Q什么是链表 A链表是由一系列结点组成的。每一个结点由两部分组成数据和指针。 203.移除链表元素 题目 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 示例 2 输入head [], val 1 输出[] 示例 3 输入head [7,7,7,7], val 7 输出[] 思路 需要遍历当元素等于val指针指向下下个元素的。第一次学习并使用链表需要熟悉如何建立链表如何遍历元素。所以一刷基本属于照猫画虎但是重要的掌握思路我也不求一遍就通透。 代码 # Definition for singly-linked list. 定义单链表
# class ListNode: 定义链表的类
# def __init__(self, val0, nextNone):
# 链表中的数据和指针nextNone是最后一个结点的属性即指针指向空\
# 但是在此处有2种指向如果有下一个结点可以再给next赋值没有就让它默认指向空
# self.val val
# self.next next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:# 创建虚拟头部节点简化删除过程因为有可能第一个结点就需要删除dummy_head ListNode(nexthead)# 遍历链表删除val的值cur dummy_headwhile cur.next: # 只要当前结点的下一个结点不为空就循环if cur.next.val val:cur.next cur.next.next # 跳过val值也就是删除该值的动作else:cur cur.next # 如果不等与val,继续遍历return dummy_head.next # 返回虚拟头节点的指针也就是去除了val值的新链表707.设计链表 题目 你可以选择使用单链表或者双链表设计并实现自己的链表。 单链表中的节点应该具备两个属性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 的节点。 示例 输入 [MyLinkedList, addAtHead, addAtTail, addAtIndex, get, deleteAtIndex, get] [[], [1], [3], [1, 2], [1], [1], [1]] 输出 [null, null, null, null, 2, null, 3] 解释 MyLinkedList myLinkedList new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1-2-3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在链表变为 1-3 myLinkedList.get(1); // 返回 3 思路 这道题目非常经典涵盖了链表基本的操作。题目看起来复杂基本是如下几个问题 在头部插入新节点在尾部插入新节点在中间插入新节点删除指定的结点 卡哥强调需要注意的是新增结点的时候要让新结点先指向下一个结点再让上一个结点指向新节点顺序很重要。 代码 1、单链表 # 定义一个链表:
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass MyLinkedList: # 单链表# 初始化链表def __init__(self):self.dummy_head ListNode() # 建立虚拟节点self.size 0 # 初始化结点的长度为0也就是刚开始链表没有任何数字# 获取下标的值def get(self, index: int) - int:if index 0 or index self.size: # 在链表之外的范围不符合return -1cur self.dummy_head.next # 必须要用self,for i in range(index):cur cur.next # 表示将指针移动到下一个结点return cur.val# 在头部新增一个结点def addAtHead(self, val: int) - None:self.dummy_head.next ListNode(val,self.dummy_head.next) # 虚拟结点指向新节点self.size 1## 在头部新增一个结点# 加入自己理解写的看下来和双链表比较接近# def addAtHead(self, val: int) - None:# new_node ListNode(val) # 创建新节点# new_node.next self.dummy_head.next # 新节点指向头节点# self.dummy_head.next new_node # 虚拟结点指向新节点# self.size 1# 在尾部添加一个结点def addAtTail(self, val: int) - None:# new_node_tail ListNode(val)cur self.dummy_head # 指针当前指向虚拟节点while cur.next: # 当当前指针没有指向空则一直循环cur cur.nextcur.next ListNode(val)self.size 1# 在指定下标添加一个结点def addAtIndex(self, index: int, val: int) - None:if index 0 or index self.size:returncur self.dummy_head# new_node3 ListNode(val)for i in range(index):cur cur.nextcur.next ListNode(val,cur.next)self.size 1# 删除指定下标的结点def deleteAtIndex(self, index: int) - None:if index 0 or index self.size: # 这里的非常重要debug了很久很久……returncur self.dummy_headfor i in range(index):cur cur.next # 在链表中遍历至索引位置的前一个结点cur.next cur.next.next # index这个位置的数就等于它的下一个数就实现了删除index指向的数self.size - 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 MyLinkedList: 2、双链表 ……暂时还不能完全理解双链表先把单链表学会了再来…… 【总结】 链表的基本操作和思路已经理解但是一些临界的条件考虑的还不够周全甚至写起代码相当生涩。继续加油吧 206.反转链表 题目 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例 1 输入head [1,2,3,4,5] 输出[5,4,3,2,1] 示例 2 输入head [1,2] 输出[2,1] 示例 3 输入head [] 输出[] 思路 让每一个结点的指针指向前一个结点。 代码 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:prevNone # 前一个结点curhead # 当前结点nextNone # 下一个结点while cur:nextcur.nextcur.nextprev # 实现反转prevcurcurnextreturn prev 今日总结 学到新知识的感觉很踏实但是一次也没有办法消化三道题对我来说在学习的过程中手写是很有用的学习到链表的基础知识并在做题中了解逻辑明日继续加油
