C++将二叉树转为双向链表及判断两个链表是否相交-北京尧图网络

前言这篇把两个常被放在一起问的指针操作题放在一篇里讲。第一题是把一棵二叉搜索树binary search tree, BST原地转换成一个有序的双向链表不新建结点只改写指针第二题是判断两个单链表是否相交如果相交找出第一个公共结点。两题的共同点是都不复杂但都要求对指针的生命周期和遍历顺序有清晰的把握写错一步就会丢链、成环或访问空指针。先说明前提。第一题针对的是二叉搜索树不是任意二叉树——只有 BST 的中序遍历才天然有序转换后的链表才有「有序」这个性质。如果题目给的是普通二叉树转换仍然可以做但结果只是某种遍历序不保证有序。第二题讨论的是无环单链表如果链表可能有环必须先判环并求出入口否则「走到末尾比长度」这一步就会死循环。两题都不需要额外分配结点。第一题的时间是 O(n)空间是递归栈的 O(h)h 为树高第二题的长度差法是 O(mn) 时间、O(1) 空间双指针切换法同样是 O(mn) 时间和 O(1) 空间。下面分别讲原理再给完整代码。一、中序遍历与双向链表的对应关系二叉搜索树的性质是左子树的所有键小于根右子树的所有键大于根。中序遍历左、根、右因此按从小到大的顺序访问每个结点。把它拉直成链表访问顺序就是链表顺序。问题在于树结点只有left和right两个指针双向链表需要prev和next。原地转换的做法是复用这两个指针把left当成prev把right当成next。这样不需要新增字段也不需要复制数据。转换的核心是一个「上一个访问过的结点」指针。中序遍历到当前结点时当前结点的left指向prev如果prev非空让prev-right指向当前结点如果prev为空说明当前是第一个结点记下它作为链表头把prev更新为当前结点继续遍历右子树。这里的关键顺序是修改当前结点的left必须在递归完左子树之后因为左子树还要用原来的left指针修改prev-right不影响尚未遍历的右子树因为prev是已经访问完的结点。还有一处容易忽略树的最右结点中序最后访问的结点的right原本就是空指针转换后它成为链表尾right保持空是正确的。链表头的left被设为prev而第一个结点的prev是空所以头结点的left也是空。这两端不需要额外处理前提是转换过程中没有把right乱改。递归写法最直观但递归深度等于树高。对平衡树是 O(log n)对退化成链的树是 O(n)后者在结点很多时可能栈溢出。工程上如果要处理任意形状的树可以改成显式栈的中序遍历逻辑完全一样只是把「递归调用」换成「压栈」。二、链表相交的判定两个单链表相交指的是它们从某个结点开始共用同一段后继形状像字母 Y而不是 X。因为每个结点只有一个next一旦两个链表在某个结点重合之后的所有结点必然完全相同。这也意味着相交的两个无环链表尾结点一定是同一个。最直接的做法是用哈希集合存下第一条链表的所有结点指针再遍历第二条看是否出现过。时间 O(mn)空间 O(m)。这个做法简单但需要额外空间而且比较的必须是指针而不是值——值相同的两个不同结点不算相交。长度差法的空间是 O(1)先分别求两条链表的长度让较长的先走长度差步然后两个指针同步前进第一次相遇的结点就是第一个公共结点。如果走到空还没相遇就不相交。双指针切换法更巧妙代码也短两个指针分别从两个头出发走到空就切换到另一条链表的头继续走。若相交它们会在第一个公共结点相遇若不相交它们会同时走到空。原因是两个指针走过的总路程都是 mn速度相同所以同时到达终点若存在公共段公共段之前的长度差会被「切换」抵消。需要强调双指针切换法只在无环链表上成立。如果链表有环指针永远不会走到空循环不会结束。所以题目若没有明确说「无环」正确顺序是先判环快慢指针再处理相交两个都有环的链表还要求入口结点相同才可能相交。本文按无环处理环的情况在坑点里说明。三、完整代码先定义两种结点。树结点复用left/right作为前驱后继链表相交部分使用单独的单链表结点避免语义混淆。// 适用于 C17#include cstddefstruct TreeNode {int val 0;TreeNode* left nullptr;TreeNode* right nullptr;};struct ListNode {int val 0;ListNode* next nullptr;};3.1 BST 转双向链表// 适用于 C17namespace bst_list {// prev 为上一个访问的结点head 为链表头仅在第一次访问时写入void inorder(TreeNode* cur, TreeNode* prev, TreeNode* head) {if (cur nullptr) {return;}inorder(cur-left, prev, head);cur-left prev; // left 复用为 previf (prev ! nullptr) {prev-right cur; // right 复用为 next} else {head cur; // 第一个结点就是链表头}prev cur;inorder(cur-right, prev, head);}// 返回链表头空树返回 nullptrTreeNode* toList(TreeNode* root) {TreeNode* prev nullptr;TreeNode* head nullptr;inorder(root, prev, head);return head;}} // namespace bst_listprev和head都用引用传递保证递归过程中共享同一份状态。prev在调用前必须初始化为空head也是如果复用同一组变量连续转换多棵树忘记重置会得到错误的头指针。转换完成后从头沿着right走应当得到升序序列从尾沿着left走应当得到降序序列。检查时可以同时核对头结点的left为空、尾结点的right为空、每个结点的next-prev指回自己。最后一条是双向链表最容易漏的树转换只设置了「当前指向前驱」和「前驱指向当前」两个方向都已经覆盖但仍建议写一个检查函数确认。3.2 判断两个链表是否相交先给长度差法思路最清晰// 适用于 C17namespace list_intersect {int length(const ListNode* head) {int n 0;for (const ListNode* p head; p ! nullptr; p p-next) {n;}return n;}// 返回第一个公共结点不相交返回 nullptr。要求两条链表无环ListNode* firstCommonNode(ListNode* headA, ListNode* headB) {if (headA nullptr || headB nullptr) {return nullptr;}int lenA length(headA);int lenB length(headB);ListNode* longer headA;ListNode* shorter headB;int diff lenA - lenB;if (diff 0) {longer headB;shorter headA;diff -diff;}for (int i 0; i diff; i) {longer longer-next; // diff 小于较长链表的长度不会走空}while (longer ! nullptr shorter ! nullptr longer ! shorter) {longer longer-next;shorter shorter-next;}return longer; // 同时为空说明不相交}再给双指针切换法代码更短但同样要求无环// 适用于 C17ListNode* firstCommonNodeTwoPointer(ListNode* headA, ListNode* headB) {ListNode* a headA;ListNode* b headB;while (a ! b) {a (a nullptr) ? headB : a-next;b (b nullptr) ? headA : b-next;}return a; // 相交时是公共结点不相交时两者同时为空}循环终止条件写成a ! b就够了。若不相交两个指针各自走完 mn 步后同时变成空循环结束并返回空若相交它们在第一个公共结点相等循环结束。这里没有额外的计数器也不需要先求长度。四、复杂度与边界任务时间额外空间备注BST 转双向链表递归O(n)O(h) 递归栈h 为树高退化树为 O(n)BST 转双向链表显式栈O(n)O(h) 显式栈避免深递归相交判定哈希集合O(mn)O(m)实现最简单相交判定长度差O(mn)O(1)需要先求长度相交判定双指针切换O(mn)O(1)要求无环边界情况要逐个确认空树返回空链表单结点树转换后头尾都是它自己left和right都为空两条链表其中一条为空时不可能相交两条链表是同一个头指针时第一个公共结点就是它本身两条链表等长且不相交时长度差为 0同步走到空返回空。还有一个语义问题题目说的「相交」通常指结点共享而不是值相等。两个值都为 5 的独立结点不是公共结点。所有实现都必须比较指针不能比较val。常见坑点1. 转换时新建结点❌ 遍历树时new TreeNode复制值另建一条链表。 ✅ 原地改写left/right题目通常要求不额外分配结点。2. 先改 right 再递归右子树❌ 在进入右子树前把cur-right改成别的导致右子树丢失。 ✅ 先递归左子树再处理当前结点与前驱的链接最后递归右子树需要改指针时先保存原来的right。3. 头指针用局部变量返回❌ 在递归函数里定义TreeNode* head nullptr;每层各有一份最后返回的是某一层的空指针。 ✅ 用引用参数或返回结构体让所有递归层共享同一个头指针。4. 忘记重置 prev 和 head❌ 复用同一组变量连续转换两棵树第二棵的头指针还是第一棵的。 ✅ 每次转换前把prev、head都置空。5. 相交判断比较值❌if (p-val q-val) return p;—— 值相同不代表同一结点。 ✅ 比较p q即地址是否相同。6. 双指针切换法用于有环链表❌ 链表有环时a、b永远不为空while (a ! b)死循环。 ✅ 先判环有环时要求两个入口结点相同再单独处理。7. 长度差法没处理空链表❌ 直接对空指针求长度后继续走diff步解引用空指针。 ✅ 入口处先判断任一为空就返回空。8. 转换后尾结点的 next 没置空❌ 手工拼接时保留了原来的右孩子指针链表成环或串到别的结点。 ✅ 中序最后访问的结点其right本来就是空若手写其他方案显式把尾结点right置空。总结要点BST 转双向链表链表相交核心思路中序遍历复用 left/right 作 prev/next对齐起点后同步前进或双指针切换关键状态前驱指针 prev、头指针 head长度差或两指针走完全程时间O(n)O(mn)空间O(h) 递归栈O(1)前提二叉搜索树无环单链表易错点丢右子树、头指针不共享比较值、忽略环两题都不需要复杂算法考的是指针操作的顺序和边界。第一题记住「左递归 → 改 left → 接 prev → 递归右」这个次序第二题记住「比较地址不比较值、有环先判环」实现就不会出大问题。

C++将二叉树转为双向链表及判断两个链表是否相交

相关推荐

SSD硬盘测速工具AS SSD Benchmark：四项指标解读与跑分避坑

C#高性能Socket通信库设计与高并发优化实践

010 Editor二进制解析：模板与脚本定位配置块

更多资讯

《AI 推文三天百万播放 0-1 分享》

【AI职场提效系列 01】职场邮件不用愁，AI 3分钟搞定高质量草稿

Behringer 推 300 美元开源 DJ 一体机，四通道价格砍到对手零头

笔记++24

笔记++25

写入用 ZSet，读取当 List？拆解一套真实零售 SaaS 的促销缓存翻车记

今日更新

GUI自动化测试中的ScreenLayout：从硬编码坐标到声明式画面地图

LLC谐振变换器12V25A 300W开关电源设计与调试全攻略

ESP32多应用Flash数据隔离：分区表与NVS namespace实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？