网络营销推广方案的思路及步骤解析_seo公司官网_百度网盘优化_查数据的网站有哪些

链表常见操作总结

1. 链表的定义

单链表节点定义

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next

双向链表节点定义

class DoublyListNode:def __init__(self, val=0, prev=None, next=None):self.val = valself.prev = prevself.next = next

2. 链表基本操作

1 插入节点

头插法

def insert_at_head(head, val):new_node = ListNode(val)new_node.next = headreturn new_node  # 返回新的头节点

尾插法

def insert_at_tail(head, val):new_node = ListNode(val)if not head:return new_nodecur = headwhile cur.next:cur = cur.nextcur.next = new_nodereturn head

2 删除节点

删除指定值的节点

def delete_node(head, val):dummy = ListNode(0)dummy.next = headprev, cur = dummy, headwhile cur:if cur.val == val:prev.next = cur.nextbreakprev, cur = cur, cur.nextreturn dummy.next

3 反转链表

反转整个链表

def reverse_list(head):prev, cur = None, headwhile cur:next_node = cur.nextcur.next = prevprev = curcur = next_nodereturn prev  # 新的头节点

反转长度为k的链表(k个一组反转链表)

def reverseKGroup(head, k):# 先检查是否有至少 k 个节点temp, count = head, 0while temp and count < k:temp = temp.nextcount += 1# 如果长度不足 k，则直接返回原链表头部if count < k:return head# 反转 k 个节点prev, curr = None, headfor _ in range(k):next_node = curr.nextcurr.next = prevprev = currcurr = next_node# 递归处理后续的部分，并连接head.next = reverseKGroup(curr, k)return prev  # 返回翻转后的新头节点

4 快慢指针

查找中间节点

def find_middle(head):slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextreturn slow

检测链表是否有环

def has_cycle(head):slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False

找到环的起点

def detect_cycle(head):slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:ptr = headwhile ptr != slow:ptr = ptr.nextslow = slow.nextreturn ptr  # 环的起点return None

5 其他

合并两个有序链表

def merge_two_lists(l1, l2):dummy = ListNode(0)cur = dummywhile l1 and l2:if l1.val < l2.val:cur.next, l1 = l1, l1.nextelse:cur.next, l2 = l2, l2.nextcur = cur.nextcur.next = l1 if l1 else l2return dummy.next

分割链表

def splitList(head, size):# 先找到 next_head 的前一个节点cur = headfor _ in range(size - 1):if cur is None:breakcur = cur.next# 如果链表长度 <= sizeif cur is None or cur.next is None:return None  # 不做任何操作，返回空节点next_head = cur.nextcur.next = None  # 断开 next_head 的前一个节点和 next_head 的连接return next_head

判断两个链表是否相交

def get_intersection_node(headA, headB):if not headA or not headB:return Nonea, b = headA, headBwhile a != b:a = a.next if a else headBb = b.next if b else headAreturn a