当前位置：首页 > news >正文

链表知识点以及习题

news 2026/6/23 16:23:54

一、什么是链表

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-> 已经是尾巴节点了”