LeetCode100-160相交链表【链表介绍】
本文基于各个大佬的文章
上点关注下点赞，明天一定更灿烂！
前言
Python基础好像会了又好像没会，所有我直接开始刷leetcode一边抄样例代码一边学习吧。本系列文章用来记录学习中的思考，写给自己看的，也欢迎大家在评论区指导~
您的每一条评论都会让我更有学习的动力。
一、分析题目
完犊子，链表，依稀记得这个名词，听这就很可怕。这次逃不掉了，学习一下链表吧
我参考了b站这个up主的讲解【1_10分钟搞定链表（python编码实现）】1_10分钟搞定链表（python编码实现）_哔哩哔哩_bilibili
认识链表
链表（Linked List） 是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域，指针域存储下一个节点的地址
与数组的对比：
- 数组：元素在内存中连续存储，通过索引访问
- 链表：元素在内存中分散存储，通过指针连接
链表的特性：
- 动态大小：可以根据需要动态增长或缩小
- 插入删除高效：在已知位置插入或删除节点只需O(1)时间
- 随机访问低效：访问第i个元素需要O(n)时间
- 内存利用率高：不需要预先分配固定大小的内存空间
链表的类型
单链表：单链表（Singly Linked List） 是最简单的链表结构，每个节点只有一个指向下一个节点的指针
双链表：双链表（Doubly Linked List） 每个节点有两个指针，分别指向前一个节点和后一个节点
循环链表：循环链表（Circular Linked List） 是一种特殊的单链表，最后一个节点的指针指向头节点，形成一个环
链表的结构定义
节点类定义
class ListNode:def __init__(self, val=0):self.val = val # 数据域，存储节点值self.next = None # 指针域，指向下一个节点链表类定义
class LinkedList:"""链表类"""def __init__(self):self.head = None # 头节点，初始为空self.size = 0 # 链表长度，初始为0def __str__(self):"""打印链表，格式为: 1 → 2 → 3 → None"""result = []current = self.headwhile current:result.append(str(current.val))current = current.next #指向下一个节点return " → ".join(result) + " → None"def __len__(self):"""返回链表长度"""return self.size判断链表是否为空
def is_empty(self):"""判断链表是否为空"""return self.size == 0查找元素
按值查找
def find_by_value(self, val):"""按值查找节点，返回第一个匹配节点，未找到返回None"""current = self.headwhile current:if current.val == val:return currentcurrent = current.nextreturn None按位置查找
def find_by_index(self, index):"""按索引查找节点（0-based），返回节点，索引无效返回None"""if index < 0 or index >= self.size:return Nonecurrent = self.headfor _ in range(index):current = current.nextreturn current插入元素
头部插入
def insert_at_head(self, val):"""在链表头部插入节点"""# 创建新节点，其next指向当前头节点new_node = ListNode(val, self.head)# 更新头节点为新节点self.head = new_nodeself.size += 1尾部插入
def insert_at_tail(self, val):"""在链表尾部插入节点"""new_node = ListNode(val)# 如果链表为空，直接将新节点作为头节点if self.is_empty():self.head = new_nodeelse:# 遍历到最后一个节点current = self.headwhile current.next is not None:current = current.next# 将最后一个节点的next指向新节点current.next = new_nodeself.size += 1指定位置插入
def insert_at_position(self, val, index):"""在指定索引位置插入节点（0-based）"""if index < 0 or index > self.size:raise IndexError("Index out of range")# 在头部插入if index == 0:self.insert_at_head(val)return# 在中间或尾部插入new_node = ListNode(val)# 找到目标位置的前一个节点prev_node = self.find_by_index(index - 1)# 插入新节点new_node.next = prev_node.nextprev_node.next = new_nodeself.size += 1修改元素
def update_by_index(self, index, new_val):"""修改指定索引位置节点的值"""node = self.find_by_index(index)if not node:raise IndexError("Index out of range")node.val = new_valreturn True删除元素
头部删除
def delete_head(self):"""删除头部节点，返回删除节点的值"""if self.is_empty():raise IndexError("Cannot delete from empty list")# 保存头节点的值val = self.head.val# 将头节点指向下一个节点self.head = self.head.nextself.size -= 1return val尾部删除
def delete_tail(self):"""删除尾部节点，返回删除节点的值"""if self.is_empty():raise IndexError("Cannot delete from empty list")# 如果只有一个节点if self.size == 1:return self.delete_head()# 找到倒数第二个节点prev_node = self.find_by_index(self.size - 2)# 保存最后一个节点的值val = prev_node.next.val# 将倒数第二个节点的next设为Noneprev_node.next = Noneself.size -= 1return val指定位置删除
def delete_at_position(self, index):"""删除指定索引位置的节点（0-based），返回删除节点的值"""if index < 0 or index >= self.size:raise IndexError("Index out of range")# 删除头部节点if index == 0:return self.delete_head()# 找到目标位置的前一个节点prev_node = self.find_by_index(index - 1)# 保存要删除节点的值val = prev_node.next.val# 将要删除节点的前一个节点的next指向要删除节点的nextprev_node.next = prev_node.next.nextself.size -= 1return val二、思路以及代码
为毛线这个题目的分类是简单，简单吗？？？这两个字好像是对我智商的侮辱。。。
结合一下样例看看，y1s1，输入都给出了目标val对于每个链表的位置啊，那倒是好搞多了。
好搞我也不会
题解哥我来了160. 相交链表 - 力扣（LeetCode）
大佬就是大佬啊，几行代码就敲明白了。所以思路真的超级超级重要，思路简单容易实现，代码的可塑性才能更强。这个算法的关键巧妙之处在于，它通过让两个指针“交换”一次链表，来抵消两个链表长度的差异。
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:# 初始化两个指针，分别指向链表 A 和链表 B 的头节点。p, q = headA, headB# 这是一个循环，直到两个指针指向同一个节点。while p is not q:# 如果指针 p 到达了链表 A 的末尾 (None)，就让它指向链表 B 的头节点。# 否则，就让它前进到链表 A 的下一个节点。p = p.next if p else headB# 如果指针 q 到达了链表 B 的末尾 (None)，就让它指向链表 A 的头节点。# 否则，就让它前进到链表 B 的下一个节点。q = q.next if q else headA# 当循环结束时，p 和 q 指向同一个节点（交点，或者都是 None）。# 返回这个节点。return p
三、本题收获
成为大佬第一步：抄大佬的代码
总结
只会打暴力，基础一团糟，明天再学吧老铁，别真学会了。