跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客工具镜像开源精选AI社区
我的书AI 学习话题UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C++算法

链表核心算法实战:从基础操作到复杂结构

链表核心算法实战涵盖两数相加、节点交换、重排、K 个升序链表合并及 K 组翻转五大经典题目。重点讲解模拟法、双指针、堆优化及分治策略在 C++ 中的实现细节,提供虚拟头结点、原地反转等关键技巧的实战代码。

道系青年发布于 2026/3/26更新于 2026/11/1585 浏览

链表是数据结构面试中的高频考点,掌握其操作技巧至关重要。下面整理了五道经典题目,涵盖模拟、指针操作、堆与分治等核心思路。

1. 两数相加

思路分析: 两个链表都是逆序存储数字的,个位对个位,十位对十位。直接遍历相加即可,关键在于处理进位。如果最后还有进位,需要额外创建一个节点存储最高位。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1, *cur2 = l2;
        ListNode* newhead = new ListNode(0); // 虚拟头结点
        ListNode* head = newhead;            // 尾指针
        int t = 0;                           // 记录进位
        
        while(cur1 || cur2 || t){
            if(cur1){
                t += cur1->val;
                cur1 = cur1->next;
            }
            if(cur2){
                t += cur2->val;
                cur2 = cur2->next;
            }
            ListNode* tmp = new ListNode(t % 10);
            head->next = tmp;
            head = head->next;
            t /= 10;
        }
        head = newhead->next;
        delete newhead;
        return head;
    }
};

2. 两两交换链表中的节点

思路分析: 通过画图辅助理解指针指向会更直观。这里使用虚拟头结点简化边界处理,注意交换时指针断链和重连的顺序,避免死循环或丢失节点。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* newhead = new ListNode(0, head);
        ListNode* prev = newhead, *cur = newhead->next;
        ListNode* next = cur->next, *nnext = cur->next->next;
        
        while(cur && next){
            // 交换结点
            prev->next = next;
            cur->next = nnext;
            next->next = cur;
            
            // 为修改下一对结点做准备
            prev = cur;
            cur = nnext;
            if(cur) next = cur->next;
            if(next) nnext = next->next;
        }
        head = newhead->next;
        delete newhead;
        return head;
    }
};

3. 重排链表

思路分析: 这道题的核心策略可以拆解为三步:先找中间节点将链表一分为二,接着将第二条链表逆序,最后合并两条链表。

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next || !head->next->next) return;
        
        ListNode* slow = head, *fast = head;
        // 找到中间结点,将链表断开
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* head2 = new ListNode(0);
        ListNode* cur = slow->next;
        slow->next = nullptr;
        
        // 反转第二条链表,头插法
        while(cur){
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        
        // 合并两条链表
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        ListNode* cur1 = head, *cur2 = head2->next;
        while(cur1){
            prev->next = cur1;
            prev = prev->next;
            cur1 = cur1->next;
            if(cur2){
                prev->next = cur2;
                cur2 = cur2->next;
                prev = prev->next;
            }
        }
        delete head2;
        delete ret;
    }
};

4. 合并 K 个升序链表

思路分析: 合并两个有序列表相对简单,用双指针比较即可。扩展到 K 个时,有两种主流方案:

  1. 优先队列(堆): 将所有头节点放入小根堆,每次取出最小值加入结果链表,若该节点有后继则推入堆中。时间复杂度 O(N log K)。
  2. 分治递归: 类似归并排序,将 K 个链表两两分组合并,直到只剩一个。相比逐一合并,这种平衡树式的合并方式能减少比较次数。

方法一:堆优化

class Solution {
public:
    struct cmp{
        bool operator()(ListNode* l1, ListNode* l2){
            return l1->val > l2->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for(auto l : lists){
            if(l) heap.push(l);
        }
        
        ListNode* head = new ListNode(0);
        ListNode* prev = head;
        
        while(!heap.empty()){ 
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = prev->next;
            
            if(t->next){
                t = t->next;
                heap.push(t);
            }
        }
        prev = head->next;
        delete head;
        return prev;
    }
};

方法二:分治递归

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
    
    ListNode* merge(vector<ListNode*>& lists, int left, int right){
        if(left > right) return nullptr;
        if(left == right) return lists[left];
        
        int mid = (left + right) >> 1;
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);
        return mergeTosort(l1, l2);
    }
    
    ListNode* mergeTosort(ListNode* l1, ListNode* l2){
        if(!l1) return l2;
        if(!l2) return l1;
        
        ListNode cur;
        ListNode* prev = &cur;
        cur.next = nullptr;
        
        ListNode* c1 = l1, *c2 = l2;
        while(c1 && c2){
            if(c1->val <= c2->val){
                prev->next = c1;
                c1 = c1->next;
            } else{
                prev->next = c2;
                c2 = c2->next;
            }
            prev = prev->next;
        }
        if(c1) prev->next = c1;
        if(c2) prev->next = c2;
        return cur.next;
    }
};

5. K 个一组翻转链表

思路分析: 按 k 个为一组进行分组,组内反转,并记录反转后的头尾节点以便连接前后段。可以先统计总长度确定需要翻转多少组,然后重复执行长度为 k 的局部反转逻辑。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        ListNode* cur = head;
        while(cur){
            n++;
            cur = cur->next;
        }
        
        n /= k;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;
        
        while(n--){
            ListNode* tmp = cur;
            for(int i = 0; i < k; i++){
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};

目录

  1. 1. 两数相加
  2. 2. 两两交换链表中的节点
  3. 3. 重排链表
  4. 4. 合并 K 个升序链表
  5. 方法一:堆优化
  6. 方法二:分治递归
  7. 5. K 个一组翻转链表

更多推荐文章

查看全部
  • Python 入门实战:猜数字游戏完整教程
  • 2026 年 3 月全球 AI 前沿动态与产业落地洞察
  • KingbaseES 实现 MySQL 零感迁移的技术方案与工程实践
  • CCF-GESP 一级 C++ 真题解析:手机电量显示
  • 本地语音识别实战:Whisper 隐私保护与多场景应用
  • AIGC 新兴领域发展与 99 个 AI 专业名词解释
  • 网络应用层编程入门
  • 前端消息提示组件设计与最佳实践
  • Windows 下使用 John the Ripper 与 Hashcat 破解压缩文件密码
  • Python 音乐下载工具 Musicdl 使用指南
  • 2026 年 3 月全球 AI 前沿动态与行业深度洞察
  • AI 深度早报:GTC 开幕、Agent 调试与具身智能突破
  • Flutter 三方库 eth_sig_util 在鸿蒙端的适配指南
  • 2026 年 3 月全球 AI 前沿动态与行业洞察
  • 基于 SpringBoot 的在线房屋租赁管理系统设计与实现
  • 企业微信群机器人发送 Markdown 消息及表格支持
  • Go Map 底层原理深度解析
  • OpenClaw 龙虾机器人本地部署与配置指南
  • AI Skills:用元编程思维重构前端开发工作流
  • 反射内存卡原理:PCIE-5565 架构与 FPGA 实现解析

相关免费在线工具

  • 加密/解密文本

    使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online

  • Markdown转HTML

    将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online