admin管理员组文章数量:1565367
系列文章
python coding with ChatGPT 打卡第1天| 二分查找、移除元素
python coding with ChatGPT 打卡第2天| 双指针、滑动窗口、螺旋矩阵
python coding with ChatGPT 打卡第3天| 移除链表、设计链表、反转链表
文章目录
- 两两交换链表中的节点
- Key Points
- 视频讲解
- 相关题目
- 重点分析
- 删除链表的倒数第N个节点
- Key Points
- 视频讲解
- 相关题目
- 重点分析
- 链表相交
- Key Points
- 相关题目
- 重点分析
- 环形链表 II
- Key Points
- 视频讲解
- 相关题目
- 重点分析
两两交换链表中的节点
Key Points
- 哨兵节点:在链表头部创建一个哨兵节点,它的 next 指针指向链表的头节点。这可以帮助简化边界情况的处理。
不用单独考虑处理节点为头节点的特殊情况
- 指针位置:指针必须在两个节点的前一个节点,才能处理这三个节点
视频讲解
帮你把链表细节学清楚
相关题目
24. 两两交换链表中的节点
重点分析
最后一步 pre = first_node 也可以写作 pre = pre.next.next
删除链表的倒数第N个节点
Key Points
- 如果删除第n个节点,需要将指针定位到(n-1)的位置
视频讲解
链表遍历学清楚
相关题目
19. 删除链表的倒数第N个节点
重点分析
def removeNthFromEnd(head, n):
# 创建一个虚拟节点,并将其下一个指针设置为链表的头部
dummy_head = ListNode(0, head)
# 创建两个指针,慢指针和快指针,并将它们初始化为虚拟节点
slow = fast = dummy_head
# 快指针比慢指针快 n+1 步
for _ in range(n+1):
fast = fast.next
# 移动两个指针,直到快速指针到达链表的末尾
while fast:
slow = slow.next
fast = fast.next
# 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点
slow.next = slow.next.next
return dummy_head.next
链表相交
Key Points
在两个链表上交替遍历,可以消除两个链表长度的差异。如果两个链表相交,不管它们的长度如何,两个指针总会在第二轮遍历中在相交点相遇。
相关题目
160. 链表相交
重点分析
环形链表 II
Key Points
以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。
为什么fast 走两个节点,slow走一个节点,有环的话,一定会在环内相遇呢,而不是永远的错开呢
首先第一点:fast指针一定先进入环中,如果fast指针和slow指针相遇的话,一定是在环中相遇,这是毋庸置疑的。
那么来看一下,为什么fast指针和slow指针一定会相遇呢?
可以画一个环,然后让 fast指针在任意一个节点开始追赶slow指针。
会发现最终都是这种情况, 如下图:
在推理过程中,大家可能有一个疑问就是:为什么第一次在环中相遇,slow的 步数 是 x+y 而不是 x + 若干环的长度 + y 呢?
首先slow进环的时候,fast一定是先进环来了。
如果slow进环入口,fast也在环入口,那么把这个环展开成直线,就是如下图的样子:
也就是说slow一定没有走到环入口3,而fast已经到环入口3了。
这说明什么呢?
在slow开始走的那一环已经和fast相遇了。
那有同学又说了,为什么fast不能跳过去呢? 在刚刚已经说过一次了,fast相对于slow是一次移动一个节点,所以不可能跳过去。
视频讲解
把环形链表讲清楚
相关题目
142. 环形链表II
重点分析
def detectCycle(head):
fast = head
slow = head
# 检测环的存在
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
else:
return None
# 找到环的入口
index1 = head
index2 = fast
while index1 != index2:
index1 = index1.next
index2 = index2.next
return index1
# 方法二 集合法
def detectCycle(head):
curr = head
visited = set()
while curr:
if curr in visited:
return curr
else:
visited.add(curr)
curr = curr.next
return None
版权声明:本文标题:python coding with ChatGPT 打卡第4天| 链表其他操作:两两交换、删除倒数第N个节点 链表相交 环形链表 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1726839283a1086600.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论