一、什么是链表1.1定义想象一列小火车多个节点组成的链条每节车厢就是一个 节点。每个节点里装了两样东西1.数据要存的内容比如一个数字、一个字符串2.下一节车厢的钩子指向下一个节点的引用/指针链表示意图火车头就是 头节点从车头开始一节一节往后找就能访问全部数据。最后一节车厢的钩子钩着“空”表示结尾None。1.2与数组最大的区别···数组在内存里是连续的一片像电影院连着的座位知道第一个就能算出第二个的位置。···链表的节点可以东一个西一个散落在内存各处全靠每个节点里的“钩子”连起来。1.3节点的结构一个最简单的单向节点用Python类定义class ListNode: def __init__(self, val0, nextNone): 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,val0,nextNone): 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。内部headnew_node外部head为空链表时因为外部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,curhead,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环形链表 II5.5链表的中间结点5.6删除链表的倒数第N个结点5.7相交链表5.8回文链表5.9.复制带随机指针的链表*******************************持续更新***************************************