📚 plmblog

Appearance

06-链表

📅 发表于 2026/04/02
🔄 更新于 2026/04/02
👁️ -- 次访问
📝 0 字
⏳ 0 分钟

总结 ​

题目总结 ​

1-160-相交链表

leetcode-160

  • 找出2个列表的相交节点。

核心特征

  • 节点引用相同，后续链表相同

Hash穷举判断节点相同法

  • 使用集合记录A的所有节点，再去遍历B，判断节点引用是否存在。
  • 若按顺序第一个存在的，则为相交节点。

双指针同速遍历自己和对方法

  • 两个指针以相同速度移动，遍历完自己后，再去遍历对方。

  • 如果相交：一定会在相交位置相遇。因为路程相同

    a+c+b=b+c+a

  • 如果不相交：会同时指向None

2-206-翻转链表

2-206-反转链表

  • 输入head节点，输出翻转后的head节点

迭代循环翻转链表

  • 设置prev和curr节点，依次遍历curr节点，把curr.next 链接为prev，curr更新。

递归翻转链表

  • 递归终止条件
  • 递归翻转head.next，获取head_new
  • 把当前head放到新head_new的末尾，即head.next=head
3-234-回文链表

3-234-回文链表

  • 判断是否回文链表，121, 1221, 122不是

快慢指针找中间+后半链表翻转+首尾遍历判断法

  • 快慢指针寻找中间节点

    • fast 走2步，slow 走1步
    • fast 走到末尾，slow 走到中间

  • 从slow开始翻转后半部分

    • 后半部分 链表翻转

  • 首尾双指针遍历判断

    • 从开头和末尾两个链表同步开始遍历比较

      • 如果节点不相同，则不是回文子串

      • 如果一直相同，且到末尾，则是。

4-141-环形链表

4-141-环形链表

  • 判断链表是否有环

快慢指针遍历相撞判断有环法

  • 双指针循环遍历

    • fast走2步，slow走1步

    • 只要快指针没跑出边界，就继续跑

  • 有环判断条件

    • 若快慢指针相遇，则说明有环

    • 若快指针跑出循环，则说明无环

5-142-环形链表2

leetcode-142-环形链表2

  • 判断链表是否有环，且找到入环的第一个节点

快慢指针2次相遇判断有环找入环首节点

  • 快慢指针相遇判断有环，fast走2步，slow走1步，相遇则有环
  • 若有环，相遇后
    • fast指向head，slow原地不变
    • 快慢指针同时走，再次相遇则为入环的第一个节点
6-021-合并两个有序链表

leetcode-021

  • 输入：2个升序列表
  • 输出：合并后的链表头节点

遍历比较选小合并法

  • 创建哑节点prehead，设置当前遍历节点curr=prehad
  • 依次遍历2个链表，谁小则放谁，把节点放到curr后面，更新curr
  • 循环结束后，链上某个链表剩余的内容，防止有1个链表没走完，直接链上即可
7-002-两数相加

leetcode-002

  • 输入：2个链表，表示2个非负整数
  • 特征：从头到尾，依次是个位、十位、百位、....
  • 输出：计算两个链表的求和，返回依然是同类型的链表

遍历2链表保留进位依次相加法

  • 设置哑节点dummy，当前节点curr=dummy，最终返回dummy.next

  • 存储进位carry，因为从个位开始向上加

  • 只要有 l1 or l2 or 进位，都要遍历做计算

    • 获取2个链表当前节点值，为空则为0
    • 计算当前求和、当前进位和当前位的数值
    • 建立新节点，存储当前位的数值
    • l1 l2链表后移
8-019-删除链表的倒数第 N 个结点

leetcode-019

  • 输入：头节点和N，删除 倒数 第N个节点
  • 输出：链表头节点

快指针先走n+1步找到目标节点再删除方法

  • 设置哑节点，处理头节点；设置设置快慢指针
  • fast 先走n+1步，fast和slow 再同速走
    • fast：走到末尾；slow：走向指向倒数n节点的前驱节点
  • 删除倒数第n个节点：设置slow.next为slow.next.next节点，
9-24-两两交换链表中的节点

leetcode-024

  • 两两交换 成对交换 链表中的元素。
  • prev -> 1 2 3 4，变成 prev -> 2 1 4 3

遍历成对交换法

  • 构建哑节点，设置prev=dummy，最终返回dummy.next
  • 循环遍历，至少prev后有2个节点，才做交换
    • 找出做交换的2个节点，prev.next和prev.next.next
    • 做交换prev -> node2 -> node1
    • prev 更新为node1
10-025-K个一组翻转链表

leetcode-025

  • 不是两两交换，而是k个作为一组，依次翻转小组中的元素
  • [1, 2, 3, 4, 5]
    • k=2 -> [2, 1, 4, 3, 5]
    • k=3 -> [3, 2, 1, 4, 5]

k个一组分别翻转

  • 先实现链表翻转子函数
  • 构建dummy、设置prev_group_end=dummy节点
  • while True 循环遍历，一次处理k步
    • 往前走k步，确定group的首节点和尾节点
      • 若不足k个，则已翻转完成或不足，直接返回dummy.next
    • group做组内翻转
      • 记录next_group_start，current_group_end.next置为空
      • 翻转当前group，获取头节点
    • 变更相关链接
      • pre_group 链接 翻转group：pre_group_end.next = reversed_start
      • 翻转group 链接 next_group：current_group_start.next = next_group_start
      • 更新prev_group_end=current_group_start
12-148-排序链表

leetcode-148

  • 给一个链表，进行排序

链表归并排序

  • 链表切分左右：快慢指针找到中间点，记录prev
  • 左右归并排序：对左右部分分别进行归并排序
  • 合并左右有序链表：把两个有序链表 合并成一个有序链表
13-023-合并K个升序链表

leetcode-023

  • 给k个升序的链表，请合并成一个升序的链表

最小堆合并K升序链表方法

  • 构建最小堆：将所有链表的头节点入堆
    • 堆元素(val, i, node)：值val、链表index、节点node
  • 构建哑节点dummy，设当前节点curr=dummy，不断增加节点
  • 堆有元素 持续循环
    • 最小节点 出堆：获得当前最小值，追加到链表末尾
    • 最小节点.next 入堆：最小节点的下一个节点 入堆

归并排序K升序链表方法

  • 切分左右：把所有链表 分为左边k和右边k 2部分
    • k=n//2，直接用k作为临界点，不要使用k+1
  • 左右归并排序：对左边和右边 各k个链表做递归排序，获得left_head、right_head
  • 合并左右有序链表：把左右2个有序链表，合并成1个链表
14-146-LRU缓存

leetcode-146

  • 实现满足有固定容量、最近最少使用LRU的数据结构
  • 实现构造函数、put、get等方法。

哈希和双向链表解法

  • Hash：快速查找key，o(1)访问
  • 双向链表：维护访问时序。最近访问 放头部，最久未访问 放尾部。
  • 设置head和tail 2个哨兵节点
  • move_to_head：先删除节点、再接到头部去
  • 双向链表插入：前后都要更新

堆的用法 ​

堆的用法
  • 包：heapq

常用方法

  • 列表变成堆结构，默认为最小堆：heapq.heapify(data)
  • 入堆：heapq.heappush(data, 3)
  • 出堆： val = heapq.heappop(data)
  • 只获取最小值：直接heap[0]
  • 获取n个最大的/最小的：heapq.nlargest(3, data)

最大堆

  • 默认为最小堆，可把数值全变负数
操作时间复杂度说明
构建堆 (Heapify)O(n)批量转换一个无序列表
插入 (Push)O(log⁡n)需要进行上浮调整
弹出最大值 (Pop)O(log⁡n)需要进行下沉调整
获取最大值 (Peek)O(1)直接访问 heap[0]
python
import heapq

def test_heap_construct():
    data = [5, 1, 9, 3, 7]
    heapq.heapify(data)  # 原地修改列表，变为堆结构
    print(data[0])       # 输出 1，最小值永远在首位
    print(data)


def test_heap_push_pop():
    heap = []
    heapq.heappush(heap, 3)  
    print(heap)
    heapq.heappush(heap, 1)
    heapq.heappush(heap, 2)
    print(heap)

    val = heapq.heappop(heap)  
    print(val, heap)

def test_heap_getlargest():
    heap = [11, 4, 5, 6, 7]
    heapq.heapify(heap)
    print(heap)
    print(heapq.nlargest(3, heap))  
    print(heapq.nsmallest(3, heap))  
     
def test_maxheap():
    data = [3, 1, 4, 1, 5, 9, 2]
    # 1. 将所有数值取反
    max_heap = [-x for x in data]
    # 2. 让列表具备堆结构 (原地操作，时间复杂度 O(n))
    heapq.heapify(max_heap)
    # 3. 插入元素
    heapq.heappush(max_heap, -6)
    # 4. 获取并弹出最大值
    max_val = -heapq.heappop(max_heap)
    print(f"最大值: {max_val}") # 输出: 9


def run_test_heap():
    # test_heap_construct()
    # test_heap_push_pop()
    # test_heap_getlargest()
    test_maxheap()

题目 ​

1-160-相交链表 ​

相交链表

leetcode-160-相交链表

  • 输入：两个单链表的头节点 headA 和 headB
  • 输出：两个单链表相交的起始节点，不相交则返回空。

链表相交

  • 节点引用相同，后续链表相同。
  • 两个指针以相同速度移动，遍历完自己后，再去遍历对方，一定会在相交位置相遇。
    • 路程长度：各自部分：a, b；公共部分：c
    • a + c + b = b + c + a

Hash穷举判断节点相同法 ​

Hash穷举判断节点相同法
  • 使用集合，记录A的所有节点，
  • 再去遍历B，查看是否有重复节点，若重复，则为相交节点。
python
def getIntersectionNode_hash(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    """
    使用hash，记录headA的所有节点；再去遍历headB，查看是否有重复的地方，注意链表无环，且是引用相同
    """
    if not headA or not headB:
        return None

    heada_set = set()  
    pa = headA
    pb = headB
    while pa.next:  
        heada_set.add(pa)
        pa = pa.next

    while pb.next:
        if pb in heada_set:  
            return pb 
        pb = pb.next
    return None

双指针同速遍历自己和对方法 ​

双指针同速遍历自己和对方法

核心思想

  • 两个指针以相同速度移动，遍历完自己后，再去遍历对方。
  • 如果相交：一定会在相交位置相遇。因为路程相同 a+c+b = b+c+a
  • 如果不相交：会同时指向None

关键循环

  • 两个指针不相等，就继续循环。
  • 自己遍历完成以后，就去遍历对方。
python
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    if not headA or not headB:
        return None

    # 只要两个指针不相等，就继续移动
    # 如果相交，它们会在第一个公共节点相遇
    # 如果不相交，它们会同时指向 None (因为 a+b = b+a)
    pa, pb = headA, headB
    while pa != pb:
        if pa:
            pa = pa.next  
        else:
            pa = headB  

        if pb:
            pb = pb.next   
        else:
            pb = headA  
    return pa

2-206-反转链表 ​

2-206-反转链表

2-206-反转链表

  • 输入：链表头节点
  • 输出：翻转后的链表头节点

迭代循环翻转链表 ​

笔记

核心思想

  • 设置prev和curr节点：prev = None, curr = head
  • 依次遍历curr，每个节点next指向prev；更新prev和curr
  • 最终返回prev
python
def reverseList_iterative(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head 
    while curr:
        next_node = curr.next  
        curr.next = prev  
        prev = curr
        curr = next_node
    return prev

递归翻转链表 ​

递归翻转链表

核心思想

  • 递归终止条件：head为空或无next
  • 递归翻转后半部分：返回new_head
  • 当前节点接到翻转链表的末尾：head.next 已是新的末尾节点

示例

  • 1 -> 2 -> 3 -> 4
  • 1->2, 4->3->2
  • 4->3->2->1
  • 返回4
python
def reverseList_recursion(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 递归终止条件
    if not head or not head.next:
        return head

    # 递归反转后部分
    new_head = self.reverseList_recursion(head.next)  

    # 当前节点接到翻转链表的后面，此时head.next已是末尾的节点
    head.next.next = head  
    head.next = None
    return new_head

3-234-回文链表 ​

回文链表

3-234-回文链表

题目

  • 给一个单链表，判断是否为回文链表。
  • 回文链表：
    • 1 2 2 1 是
    • 1 2 3 2 1 是
    • 1 2 2：不是

快慢指针找中间+后半链表翻转+首尾遍历判断法 ​

双指针+链表翻转解决回文链表

快慢指针寻找中间节点

  • fast 走2步，slow 走1步
  • fast 走到末尾，slow 走到中间

从slow开始翻转后半部分

  • 后半部分 链表翻转

首尾双指针遍历判断

  • 从开头和末尾两个链表同步开始遍历比较

    • 如果节点不相同，则不是回文子串

    • 如果一直相同，且到末尾，则是。

python
def isPalindrome_twopointer(self, head: Optional[ListNode]) -> bool:
    if not head or not head.next:
        return True

    # slow走到中间，或者中间的下一个位置
    slow = fast = head 
    while fast and fast.next:  
        slow = slow.next
        fast = fast.next.next

    # 从slow开始翻转链表
    pre = None
    cur = slow 
    while cur:  
        next_node = cur.next
        cur.next = pre 
        pre = cur
        cur = next_node

    # 从两个链表开始找，同时走，同时比较
    p1, p2 = head, pre 

    is_same = True
    while p2:  
        # 注意以p2为循环，因为p2反转后，p2末尾为None
        # p1末尾则一直指向p2的开头
        if p1.val != p2.val:  
            is_same = False
            break
        p1 = p1.next
        p2 = p2.next
    return is_same

4-141-环形链表 ​

4-141-环形链表

4-141-环形链表

  • 判断链表是否有环

快慢指针相遇判断有环 ​

快慢指针相遇判断有环

  • 双指针循环遍历

    • fast走2步，slow走1步

    • 只要快指针没跑出边界，就继续跑

  • 有环判断条件

    • 若快慢指针相遇，则说明有环

    • 若快指针跑出循环，则说明无环

python
def hasCycle_two_pointer(self, head: Optional[ListNode]) -> bool:
    # 如果链表为空或只有一个节点且无环，直接返回 False
    if not head or not head.next:
        return False

    slow = head
    fast = head

    # 只要快指针没跑出边界，就继续跑
    while fast and fast.next:  
        slow = slow.next          # 慢指针走 1 步
        fast = fast.next.next     # 快指针走 2 步

        # 如果撞上了，说明有环
        if slow == fast:  
            return True

    # 跑出循环说明快指针到头了，没环
    return False

5-142-环形链表2 ​

5-142-环形链表2

leetcode-142-环形链表2

  • 判断链表是否有环，且找到入环的第一个节点

快慢指针2次相遇判断有环找入环首节点 ​

快慢指针2次相遇
  • 快慢指针相遇判断有环，fast走2步，slow走1步，相遇则有环
  • 若有环，相遇后
    • fast指向head，slow原地不变
    • 快慢指针同时走，再次相遇则为入环的第一个节点
python
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head

    # 1. 寻找相遇点
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:  
            # 2. 找到相遇点后，寻找入口
            # 将 fast 放回起点，slow 留在原地
            fast = head
            while fast != slow:  
                fast = fast.next # 此时两人都只走 1 步
                slow = slow.next
            # 相遇处即为入口
            return fast  
    return None

6-021-合并两个有序链表 ​

6-021-合并两个有序链表

leetcode-021

  • 输入：2个升序列表
  • 输出：合并后的链表头节点

遍历比较选小合并法 ​

遍历比较选小合并法
  • 创建哑节点prehead，设置当前遍历节点curr=prehad
  • 依次遍历2个链表，谁小则放谁，把节点放到curr后面，更新curr
  • 循环结束后，链上某个链表剩余的内容，防止有1个链表没走完，直接链上即可
python
def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    # 创建哑节点，作为新链表的“锚点”
    prehead = ListNode(-1)  
    curr = prehead  

    # 当两个链表都不为空时，比较头节点
    while l1 and l2:
        if l1.val <= l2.val:  
            curr.next = l1  
            l1 = l1.next  
        else:
            curr.next = l2
            l2 = l2.next
        # 移动新链表的当前指针
        curr = curr.next  

    # 只要有一个链表走完了，就把另一个链表剩下的部分直接接上
    # 因为剩下的部分本身就是有序的
    if l1:
        cur.next = l1
    elif l2:
        cur.next = l2 

    return prehead.next

7-002-两数相加 ​

7-002-两数相加

leetcode-002

  • 输入：2个链表，表示2个非负整数
  • 特征：从头到尾，依次是个位、十位、百位、....
  • 输出：计算两个链表的求和，返回依然是同类型的链表

遍历2链表保留进位依次相加 ​

遍历2链表保留进位依次相加法

  • 设置哑节点dummy，当前节点curr=dummy，最终返回dummy.next

  • 存储进位carry，因为从个位开始向上加

  • 只要有l1 or l2 or 进位，都要遍历做计算

    • 获取2个链表当前节点值，为空则为0
    • 计算当前求和、当前进位和当前位的数值
    • 建立新节点，存储当前位的数值
    • l1 l2链表后移
python
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    # 使用哑节点简化操作
    dummy = ListNode(0)  
    curr = dummy  
    carry = 0  # 存储进位

    # 只要 l1 或 l2 还没走完，或者还有进位没处理
    while l1 or l2 or carry:  
        # 取值，如果链表已经空了则取 0
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # 计算当前位的和及进位
        total = val1 + val2 + carry  
        carry = total // 10       # 新的进位
        current_val = total % 10   # 当前位的结果

        # 建立新节点
        curr.next = ListNode(current_val)
        curr = curr.next

        # 链表指针后移
        if l1: l1 = l1.next  
        if l2: l2 = l2.next  

    return dummy.next

8-019-删除链表的倒数第 N 个结点 ​

8-019-删除链表的倒数第 N 个结点

leetcode-019

  • 输入：头节点和N，删除 倒数 第N个节点
  • 输出：链表头节点

快慢指针走n+1步找到目标节点 ​

快慢指针走n步找到目标节点

  • 设置哑节点，处理头节点；设置设置快慢指针

  • fast 先走n+1步，fast和slow 再同速走

    • fast：走到末尾；slow：走向指向倒数n节点的前驱节点

  • 删除倒数第n个节点：设置slow.next为slow.next.next节点，

python
def removeNthFromEnd_mf(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    # 哑节点，解决删除头节点的情况
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy

    # fast 先走n+1步，这样slow刚刚指向倒数第n个节点的前驱节点
    for _ in range(n+1): 
        fast = fast.next

    while fast:
        slow = slow.next
        fast = fast.next
    # 此时slow为倒数第n个节点的前驱节点
    if slow.next.next:
        # 如果next有节点
        slow.next = slow.next.next
    else:
        # 如果next本身已是None
        slow.next = None
		# 返回真正头节点
    return dummy.next

9-24-两两交换链表中的节点 ​

9-24-两两交换链表中的节点

leetcode-024

  • 两两交换 成对交换 链表中的元素。
  • prev -> 1 2 3 4，变成 prev -> 2 1 4 3

遍历成对交换法 ​

遍历成对交换法
  • 构建哑节点，设置prev=dummy，最终返回dummy.next
  • 循环遍历，至少prev后有2个节点，才做交换
    • 找出做交换的2个节点，prev.next和prev.next.next
    • 做交换prev -> node2 -> node1
    • prev 更新为node1
python
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 哑节点
    dummy = ListNode(0, head)
    prev = dummy  

    # 至少后面有2个节点，才做交换
    while prev.next and prev.next.next:  
        # 要交换的2个节点
        node1 = prev.next
        node2 = prev.next.next

        # 做交换
        prev.next = node2
        node1.next = node2.next
        node2.next = node1

        # prev 更替，prev -> node2 -> node1，下一对的前驱是node1
        prev = node1  

    return dummy.next

10-025-K个一组翻转链表 ​

10-025-K个一组翻转链表

leetcode-025

  • 不是两两交换，而是k个作为一组，依次翻转小组中的元素
  • [1, 2, 3, 4, 5]
    • k=2 -> [2, 1, 4, 3, 5]
    • k=3 -> [3, 2, 1, 4, 5]

k个一组分别翻转 ​

k个一组分别翻转
  • 先实现链表翻转子函数
  • 构建dummy、设置prev_group_end=dummy节点
  • while True 循环遍历，一次处理k步

    • 往前走k步，确定group的首节点和尾节点

      • 若不足k个，则已翻转完成或不足，直接返回dummy.next

    • group做组内翻转

      • 记录next_group_start，current_group_end.next置为空
      • 翻转当前group，获取头节点

    • 变更相关链接

      • pre_group 链接 翻转group：pre_group_end.next = reversed_start
      • 翻转group 链接 next_group：current_group_start.next = next_group_start
      • 更新prev_group_end=current_group_start

链表翻转函数

python
def reverse_list(self, head: Optional[ListNode]):
    prev = None
    curr = head

    while curr:
        next_node = curr.next  
        curr.next = prev
        prev = curr
        curr = next_node  
    return prev

k Group 翻转函数

python
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head or k == 1:
        return head

    # 依次遍历，每k个，去执行一次链表翻转
    dummy = ListNode(0, head)
    prev_group_end = dummy  

    while True:
        # 先去找k个节点
        current_node = prev_group_end
        for _ in range(k): 
            current_node = current_node.next
            if not current_node:
                # 已不足k个，剩余的无需翻转
                return dummy.next  

        # 当前group和next group的头节点
        current_group_start = prev_group_end.next  
        current_groupt_end = current_node  
        next_group_start = current_node.next  

        # 翻转当前group，当前group尾节点next设为空，避免完全翻转
        current_groupt_end.next = None
        reversed_start = self.reverse_list(current_group_start)  

        # 变更链接
        prev_group_end.next = reversed_start  
        current_group_start.next = next_group_start  
        prev_group_end = current_group_start  
    return

11-138-随机链表的复制 ​

11-138-随机链表的复制

leetcode-138

  • 给一个链表，有next和random 2个指针；要求完全深度复制。

难点

  • random随意指向，如果某节点还没创建，该如何复制？

Hash建立新旧节点索引复制链表法 ​

Hash建立新旧节点索引复制链表法
  • 使用dict，建立原节点-新节点的索引列表
  • 再依次遍历，去设置新节点的random和next 属性
python
def copyRandomList_hash(self, head: 'Optional[Node]') -> 'Optional[Node]':
    if not head:
        return head

    # 原节点，新节点
    d = {}
    # 遍历，依次建立新节点
    curr = head
    while curr:
        d[curr] = Node(curr.val)  
        curr = curr.next

    curr = head
    while curr:
        new = d[curr]
        new.next = d.get(curr.next, None) 
        new.random = d.get(curr.random, None) 
        curr = curr.next

    return d[head]

原地修改法：依次插入新节点 ​

依次插入新节点

核心思想

  • 在每个原节点后面插入对应的新节点，原节点.next为其新节点

三次遍历步骤

  • 新节点插入：遍历原链表，为每个节点插入新节点
  • 设置新节点的random节点：new.random = curr.random.next
  • 移除链表中的旧节点：构建新链表
python
def copyRandomList_insert(self, head: 'Optional[Node]') -> 'Optional[Node]':
    if not head:
        return None

    # 1. 在每个原节点后面插入对应的新节点，每个原节点.next即为该节点的新节点
    # A -> B  => A -> A' -> B -> B'
    curr = head
    while curr:
        new = Node(curr.val)  
        new.next = curr.next
        curr.next = new
        curr = new.next

    # 2. 设置random节点
    curr = head
    while curr:
        new = curr.next
        if curr.random:
            # 注意random为空的情况
            new.random = curr.random.next
        curr = new.next 

    # 3. 拆分链表，去掉原节点
    curr = head 
    new_head = curr.next
    while curr:
        new_node = curr.next
        # 恢复原链表
        curr.next = new_node.next  
        # 设置新链表
        if new_node.next:
            new_node.next = new_node.next.next  
        curr = curr.next

    return new_head

12-148-排序链表 ​

12-148-排序链表

leetcode-148

  • 给一个链表，进行排序

链表归并排序 ​

链表归并排序
  • 切分左右：快慢指针找到中间点，记录prev
  • 左右归并排序：对左右部分分别进行归并排序
  • 合并左右有序链表：把两个有序链表 合并成一个有序链表

合并2个升序链表：

python
def merge_two_uplists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    """合并2个升序链表
    """
    dummy = ListNode(0, None)
    curr = dummy  

    p1, p2 = l1, l2 
    while p1 and p2:  
        if p1.val < p2.val:
            curr.next = p1
            p1 = p1.next
        else:
            curr.next = p2
            p2 = p2.next
        curr = curr.next

    curr.next = p1 if p1 else p2  
    return dummy.next

链表归并排序：

python
def sortList_by_merge(self, head: Optional[ListNode]) -> Optional[ListNode]:
    """ 归并排序
    """
    if not head or not head.next:  
        return head
    # 1. 切分，快慢指针找到中间点。slow指向右边部分的第一个节点
    slow = fast = head
    # 定义pre，为左边末尾节点
    pre = None 
    while fast and fast.next:
        pre = slow  
        slow = slow.next
        fast = fast.next.next

    # 2. 递归左右两边排序
    pre.next = None
    left = self.sortList_by_merge(head)  
    right = self.sortList_by_merge(slow)  

    # 3. 合并
    new_head = self.merge_two_uplists(left, right)  
    return new_head

13-023-合并K个升序链表 ​

13-023-合并K个升序链表

leetcode-023

  • 给k个 升序链表，请合并成一个 升序链表

最小堆合并K升序链表 ​

最小堆合并K升序链表

  • 构建最小堆：将所有链表的头节点入堆

    • 堆元素(val, i, node)：值val、链表index、节点node

  • 构建哑节点dummy，设当前节点curr=dummy，不断增加节点

  • 堆有元素 持续循环

    • 最小节点 出堆：获得当前最小值，追加到链表末尾
    • 最小节点.next 入堆：最小节点的下一个节点 入堆
python
def mergeKLists_heap(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    # 定义堆
    min_heap = []

    # 1. 将所有链表的头节点入堆
    # 格式为 (node.val, unique_index, node)
    # list会依次比较，需要i，因为若2个val相同，则需要比较第2个元素，但纯node是无法比较的，因此插入一个index，防止元素相同无法比较

    for i, head in enumerate(lists):
        if head:
            heapq.heappush(min_heap, (head.val, i, head))  

    dummy = ListNode(0)
    curr = dummy

    # 2. 循环处理堆
    while min_heap:
        val, i, node = heapq.heappop(min_heap)  

        # 连接到结果链表
        curr.next = node
        curr = curr.next

        # 如果该链表还有下一个节点，继续入堆
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))  

    return dummy.next

分治归并排序K升序链表 ​

归并排序K升序链表
  • 切分左右：把所有链表 分为左边k和右边k 2部分
    • k=n//2，直接用k作为临界点，不要使用k+1
  • 左右归并排序：对左边和右边 各k个链表做递归排序，获得left_head、right_head
  • 合并左右有序链表：把左右2个有序链表，合并成1个链表

合并2个有序链表 函数

python
def merge_two_uplists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    curr = dummy

    p1, p2 = l1, l2
    while p1 and p2:
        if p1.val < p2.val:
            curr.next = p1
            p1 = p1.next 
        else:
            curr.next = p2 
            p2 = p2.next 
        curr = curr.next 

    curr.next = p1 if p1 else p2 
    return dummy.next

分治合并k个列表

python
def mergeKLists_divide(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:
        return None
    if len(lists) == 1:
        return lists[0]

    # 1. 分解，分左右部分，切记直接使用k作为临界点，不要使用k+1
    k = len(lists) // 2
    left_lists = lists[0:k]
    right_lists = lists[k:]

    # 2. 递归计算各部分
    left_head = self.mergeKLists_divide(left_lists) 
    right_head = self.mergeKLists_divide(right_lists) 

    # 3. 合并2个有序链表
    head = self.merge_two_uplists(left_head, right_head) 
    return head

14-146-LRU缓存 ​

14-146-LRU缓存

leetcode-146

  • 实现满足有固定容量、最近最少使用LRU的数据结构
  • 实现构造函数、put、get等方法。

哈希和双向链表解法 ​

哈希和双向链表解法
  • Hash：快速查找key，o(1)访问
  • 双向链表：维护访问时序。最近访问 放头部，最久未访问 放尾部。
  • 设置head和tail 2个哨兵节点
  • move_to_head：先删除节点、再接到头部去
  • 双向链表插入：前后都要更新

双向链表

python
class ListNode:
    """ 双向链表
    """
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value 
        self.prev = None
        self.next = None

LRU Cache

python
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        # 哨兵节点
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail 
        self.tail.prev = self.head

    def _add_to_head(self, node):
        """把节点加到开头"""
        self.head.next.prev = node 
        node.next = self.head.next 

        self.head.next = node 
        node.prev = self.head 
        return
    
    def _remove_node(self, node):
        """删除节点"""
        node.next.prev = node.prev
        node.prev.next = node.next

    def _move_to_head(self, node):
        """ 注意，先删除原节点，再插入到头节点
        """
        self._remove_node(node)  
        self._add_to_head(node)  
        return
    
    def _pop_tail(self):
        """删除末尾节点
        """
        node = self.tail.prev 
        self._remove_node(node)
        return node 

    def get(self, key: int) -> int:
        if key in self.cache:
            # 命中了，需要更新到最近访问
            node = self.cache[key]
            self._move_to_head(node)
            return self.cache[key].value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            # 更新值
            node.value = value 
            self._move_to_head(node)  
            return
        else:
            if len(self.cache) >= self.capacity:
                node = self._pop_tail()  
                del self.cache[node.key]
            node = ListNode(key, value)
            self.cache[key] = node 
            self._add_to_head(node)  
        return
总访客数：   ·   总访问量：
PLM's Blog @ 2016 - 2026