一、什么是链表
1.1定义
想象一列小火车（多个节点组成的链条），每节车厢就是一个 节点。每个节点里装了两样东西：
1.数据（要存的内容，比如一个数字、一个字符串）
2.下一节车厢的钩子（指向下一个节点的引用/指针）
火车头就是 头节点，从车头开始，一节一节往后找，就能访问全部数据。最后一节车厢的钩子钩着“空”，表示结尾（None）。
1.2与数组最大的区别：
···数组在内存里是连续的一片，像电影院连着的座位，知道第一个就能算出第二个的位置。
···链表的节点可以东一个西一个，散落在内存各处，全靠每个节点里的“钩子”连起来。
1.3节点的结构
一个最简单的单向节点，用Python类定义：
class ListNode: def __init__(self, val=0, next=None): self.val = val # 存放的数据 self.next = next # 指向下一个节点1.4链表的类型
单向链表：每个节点只知道下一个。
A → B → C → None双向链表：每个节点既知道下一个，也知道上一个。
None ← A ⇄ B ⇄ C → None循环链表：尾节点的 next 指回头节点，形成闭环。
A → B → C → A
面试绝大部分只考单向链表，双向和循环是拓展了解。
二、链表的基本操作（配了代码）
基本思路：构建一个小链表1-->2-->3，然后学习遍历，插入，删除。
2.1创建链表
#定义一个链表类 class ListNode(): def __init__(self,val=0,next=None): self.val =val #节点数据 self.next =next #节点指针2.2遍历节点（打印所有值）
node3 = ListNode(3) #尾巴节点 node2 = ListNode(2,node3) node1 = ListNode(1,node2) #头结点 def print_list(head): cur = head #节点参数赋值给cur ,可以认为cur是链表的节点变量 while cur: print(cur.val,end="->") #当节点有数据内容，打印节点，并在输出的最后加上“->” cur = cur.next print(" 已经是尾巴节点了") print_list(node1)2.3在头部插入节点
思路：要让新节点变成新的头，只需让新节点的next指向原来的头。
def insert_at_head(head,val): #在头部插入节点 new_code = ListNode(val) new_code.next = head return new_code #返回新节点 head1= node1 print_list(insert_at_head(node1,0)) #从头遍历打印2.4在尾部插入节点
思路：从头节点开始，一直利用cur.next（节点指针）指向下一个，直到下一个节点=None时，就找到了尾结点，此时只需把尾结点cur.next = None变为cur.next = new_node即可。
def insert_node_tailer(head,val): #尾部添加节点函数 new_node = ListNode(val)#实例化对象，添加新节点，名为new_node if head is None: #如果头链表为空 return new_node #把new_node作为函数返回值，当做头节点了，并且下面不执行了。 cur = head while cur.next: cur = cur.next cur.next= new_node return head #返回头节点，便于遍历打印出链表 head = insert_node_tailer(node1,4) #插入头节点和新插入节点数据 print_list(head)注意：若在函数内部，head = new_node, node1为空链表时，会一直循环输出4。
因为外部node0传入到函数形参的head为空，进入函数内部，虽然head = new_node了，最后也return head，但是这是返回函数值，并不会改变外部变量！！！
所以：
- 函数里的
head：局部变量，只在函数内部生效； - 函数外的
head：外部变量，用来保存整个链表的起点； return x：只负责把x这个数据 / 对象 “送回” 调用处，不主动修改任何变量。
2.5删除指定值的节点
边界考虑：删除需要考虑删除的是头节点还是中间节点。
思路：用一个指针遍历，同时记录前一个节点prev，找到要删的节点后，让prev.next直接跳过它指向cur.next。
def delete_by_val(head,val):#删除指定值的节点 #如果删除的节点是头节点 while head and head.val == val: # head = head.next if not head: #头结点为空时 return None #若是中间节点的话 pre,cur=head,head.next #从第二个节点开始遍历节点，设置初始值 while cur: #要删除的值不为空，即链表节点≥2时 if cur.val == val: # pre.next = cur.next #pre的下一个节点跳过cur else: pre = cur #pre节点后移一位 cur = cur.next #cur节点后移一位，两个节点变量整体后移一位 return head #链表均返回头节点，便于从头开始遍历打印 head2 = delete_by_val(node1,1) #原来为01234，删了0和1 print_list(head2) #输出结果：“1->2->3->4-> 已经是尾巴节点了”三、面试核心技巧（必须掌握）
学完基本操作后，面试题之所以难，是因为它们都是这些操作的组合变形，并需要一些巧妙的技巧。面试题目就是多个基础知识点以及技巧的综合运用！！！
3.1技巧1：虚拟头节点 (Dummy Node)
什么时候用？当需要修改头节点，又不想单独写一堆if判断时。
原理：在真正的头前面加一个假的节点，最后返回dummy.next。
例子：删除链表里所有值为val的节点（不用单独处理头节点了）。
3.2技巧2：快慢指针
3.3技巧3：反转链表（必背）
四、高频面试题思路精讲（会了解法，再看代码）
有了上面技巧的基础上，来几道常考题：
4.1合并两个有序链表
用虚拟头 + 比较两个链表头的大小，谁小接谁。最后把剩余部分挂上。
4.2删除链表的倒数第 N 个节点
快慢指针：先让快指针走n步，然后快慢一起走，快指针到末尾时，慢指针正好在倒数第 N 个的前一个。
4.3判断链表是否回文
快慢指针找中点 -> 反转后半部分链表 -> 前半部分和后半部分逐一比较 -> （可选）再反转回来。
4..4相交链表的第一个公共节点
两个指针分别从 A 和 B 头出发，走到末尾后切换到对方链表头继续走，若相遇，该节点即为交点。原理是抹平了长度差。
4.5复制带随机指针的链表
三次遍历：①在每个原节点后面插入一个拷贝节点；②设置拷贝节点的随机指针；③分离两个链表。
4.6环形链表 II（找环入口）
先快慢指针判断有环并找到相遇点；然后一个指针从头开始，一个指针从相遇点开始，同速走，相遇点就是环入口。（弗洛伊德算法）
4.7K 个一组翻转链表
4.8移除链表重复节点
五、热题训练
依次刷 LeetCode 热题：
5.1反转链表
5.2合并两个有序链表
5.3环形链表
5.4环形链表 II
5.5链表的中间结点
5.6删除链表的倒数第N个结点
5.7相交链表
5.8回文链表
5.9.复制带随机指针的链表
*******************************持续更新***************************************
