链表基础算法：Python实现指南

1. 什么是链表 链表是一种非连续存储的线性数据结构，由一系列节点通过指针连接而成。每个节点包含数据域和指针域，指针域存储着相邻节点的内存地址。与数组相比，链表在插入删除操作上更具优势，但随机访问效率较低。 主要类型包括： 单链表 双向链表 循环链表 2. 单链表 2.1 节点定义 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next 节点中的val存储数据，next指针相当于寻宝游戏中的线索，指向下一个节点位置。当next为None时，表示链表结束。 2.2 基本操作 def traverse(head): cur = head while cur: print(cur.val, end=' -> ') cur = cur.next print('None') def insert_at_head(head, val): new_node = ListNode(val) new_node.next = head return new_node def insert_at_tail(head, val): new_node = ListNode(val) if not head: return new_node cur = head while cur.next: cur = cur.next cur.next = new_node return head def delete_node(head, target): if not head: return None if head.val == target: return head.next cur = head while cur.next: if cur.next.val == target: cur.next = cur.next.next return head cur = cur.next return head def reverse_list(head): prev = None cur = head while cur: next_node = cur.next cur.next = prev prev = cur cur = next_node return prev 3.双向链表 双向链表为每个节点增加前驱指针，支持双向遍历。这种结构在需要频繁前后移动的场景中尤为实用。 节点结构包含prev和next两个指针： class DoubleListNode: def __init__(self, val=0, prev=None, next=None): self.val = val self.prev = prev self.next = next def dll_insert_head(head, val): new_node = DoubleListNode(val) new_node.next = head if head: head.prev = new_node return new_node def dll_delete_node(node): if node.prev: node.prev.next = node.next if node.next: node.next.prev = node.prev 4.循环列表 循环链表的尾节点指向头节点，形成环形结构。这种设计可以实现循环遍历。 def create_circular_list(values): if not values: return None head = ListNode(values[