济南简单网站制作排名公司,响应式网站的好处,大型公司网站建设,建设淘宝网站的人员组织结构这里写目录标题 一、141. 环形链表二、876. 链表的中间结点三、面试题 02.01. 移除重复节点 一、141. 环形链表
简单
给你一个链表的头节点 head #xff0c;判断链表中是否有环。 如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中… 这里写目录标题 一、141. 环形链表二、876. 链表的中间结点三、面试题 02.01. 移除重复节点 一、141. 环形链表
简单
给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。
示例 1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。
示例 2 输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。
示例 3 输入head [1], pos -1 输出false 解释链表中没有环。 在本题中使用快慢指针 若是链表无环那么 fast 指针会先指向 Null。 若是链表有环fast 和 slow 迟早会在环中相遇。
class Solution:def hasCycle(self, head):#如果空链表或者只有一个节点。无环if not head or head.next None:return False#初始化快慢指针slowheadfasthead#如果不存在环肯定fast指向null#细节fast每次走2步所以要确定fast和fast.next不为空不然指向报错while fast and fast.next:#快指针移动2步慢指针移动1位fastfast.next.nextslowslow.next#快慢指针相遇有环if fast slow:return Truereturn False二、876. 链表的中间结点
给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 解题思路 考虑借助快慢双指针 fast, slow 「快指针 fast」每轮走 2 步「慢指针 slow」每轮走 1 步。fast 的步数恒为 slow 的 2 倍因此当快指针遍历完链表时慢指针就指向链表中间节点。而由于长度为偶数的链表有两个中间节点因此需要分两种情况考虑 链表长度为奇数 当 fast 走到链表「尾节点」时slow 正好走到「中间节点」。 链表长度为偶数 当 fast 走到「null」时越过「尾节点」后slow 正好走到「第二个中间节点」。 总结以上规律应在当 fast 遇到尾节点或越过尾节点时跳出循环并返回 slow 即可。 执行步骤如下 class Solution:def middleNode(self,head):fastslowheadwhile fast and fast.next:fastfast.next.nextslowslow.nextreturn slow三、面试题 02.01. 移除重复节点
编写代码移除未排序链表中的重复节点。保留最开始出现的节点。
示例1: 输入[1, 2, 3, 3, 2, 1] 输出[1, 2, 3]
示例2: 输入[1, 1, 1, 1, 2] 输出[1, 2] 提示 链表长度在[0, 20000]范围内。 链表元素在[0, 20000]范围内。
进阶 如果不得使用临时缓冲区该怎么解决 题目要求删除链表中的「重复节点」并保留「最开始出现的节点」。考虑遍历链表借助一个「哈希表 Set 」记录遇到的节点值在遍历过程中判断 若当前节点在 Set 中代表是「重复节点」则删除之 若当前节点不在 Set 中代表此节点第一次遇到则将此「节点值」加入到 Set 中
class Solution:def removeDuplicateNodes(head:ListNode):preNonecurheadvset()while cur:if cur.val in v:pre.nextcur.nextelse:v.add(cur.val)precurcurcur.nextreturn head
