旅游网站介绍怎么写,个人博客网站模板源码,wordpress更换头像,哪些是门户网站这里写目录标题 一、面试题 02.02. 返回倒数第 k 个节点二、82. 删除排序链表中的重复元素 II三、141. 环形链表 一、面试题 02.02. 返回倒数第 k 个节点 提示 简单 130 相关企业 实现一种算法#xff0c;找出单向链表中倒数第 k 个节点。返回该节点的值。 注意#xff1a;本… 这里写目录标题 一、面试题 02.02. 返回倒数第 k 个节点二、82. 删除排序链表中的重复元素 II三、141. 环形链表 一、面试题 02.02. 返回倒数第 k 个节点 提示 简单 130 相关企业 实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。 注意本题相对原题稍作改动
示例 输入 1-2-3-4-5 和 k 2 输出 4 说明
给定的 k 保证是有效的。 “”
class Solution:def func1(self,head:ListNode,n,k):preheadcurheadfor i in range(k):curcur.nextwhile cur:curcur.nextprepre.nextreturn pre.val二、82. 删除排序链表中的重复元素 II 中等 1.2K 相关企业 给定一个已排序的链表的头 head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回 已排序的链表 。
示例 1
输入head [1,2,3,3,4,4,5] 输出[1,2,5] 示例 2
输入head [1,1,1,2,3] 输出[2,3]
思路
def func5(head):dummyListNode(0)dummy.nextheadcurheadpredummywhile cur:while cur.next and cur.val!cur.next.val:curcur.nextif pre.nextcur:prepre.nextelse:pre.nextcur.nextcurcur.nextreturn dummy.next
三、141. 环形链表
简单 2.1K 相关企业 给你一个链表的头节点 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.nextNone:return False#初始化快慢指针slowheadfasthead#如果不存在环肯定fast指向null# 细节fast每次走2步所有要确定fast和fast.next不为空不然指向报错while fast and fast.next:#快指针移动2步慢指针移动1步fastfast.next.nextslowslow.next#快慢指针相遇有环if fastslow:return Truereturn False
