这里写目录标题
- 一、面试题 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):
pre=head
cur=head
for i in range(k):
cur=cur.next
while cur:
cur=cur.next
pre=pre.next
return 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):
dummy=ListNode(0)
dummy.next=head
cur=head
pre=dummy
while cur:
while cur.next and cur.val!=cur.next.val:
cur=cur.next
if pre.next==cur:
pre=pre.next
else:
pre.next=cur.next
cur=cur.next
return 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.next==None:
return False
#初始化快慢指针
slow=head
fast=head
#如果不存在环，肯定fast指向null
# 细节：fast每次走2步，所有要确定fast和fast.next不为空，不然指向报错
while fast and fast.next:
#快指针移动2步，慢指针移动1步
fast=fast.next.next
slow=slow.next
#快慢指针相遇，有环
if fast==slow:
return True
return False
