6道经典算法题详解：从排序到链表，覆盖面试高频考点

6道经典算法题详解从排序到链表覆盖面试高频考点算法面试中排序算法、分治思想和链表操作是绝对的高频考点几乎是每家公司的必考题。本文精选了LeetCode中6道经典题目覆盖「三色排序」「归并排序」「逆序对统计」「链表相加」「链表两两交换」等核心场景每道题都包含题目解析、思路推导、完整C代码、复杂度分析帮你彻底吃透这些高频考点。文章目录6道经典算法题详解从排序到链表覆盖面试高频考点一、75. 颜色分类中等题目描述思路分析荷兰国旗问题完整C代码复杂度分析二、912. 排序数组中等题目描述思路分析归并排序完整C代码复杂度分析三、LCR 170. 交易逆序对的总数困难题目描述思路分析归并排序求逆序对完整C代码复杂度分析四、2. 两数相加中等题目描述思路分析链表模拟加法完整C代码复杂度分析五、24. 两两交换链表中的节点中等题目描述思路分析链表指针操作完整C代码复杂度分析六、算法核心总结1. 排序算法对比2. 链表操作核心技巧面试高频追问一、75. 颜色分类中等题目描述给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的sort函数的情况下解决这个问题。示例1输入nums [2,0,2,1,1,0] 输出[0,0,1,1,2,2]示例2输入nums [2,0,1] 输出[0,1,2]思路分析荷兰国旗问题这道题是经典的荷兰国旗问题核心是用三指针法实现原地排序时间复杂度O(n)空间复杂度O(1)定义三个指针left0的右边界初始为-1[0, left]区间全为0right2的左边界初始为n[right, n-1]区间全为2i遍历指针初始为0[left1, i-1]区间全为1遍历数组直到i right如果nums[i] 0和left1位置交换lefti交换后i位置是1直接后移如果nums[i] 1直接i1的区间扩大如果nums[i] 2和right-1位置交换right--i不后移交换后i位置是新元素需要重新判断遍历完成后数组自然按0、1、2有序。完整C代码classSolution{public:voidsortColors(vectorintnums){intnnums.size();intleft-1,rightn,i0;while(iright){if(nums[i]0){swap(nums[left],nums[i]);}elseif(nums[i]1){i;}else{swap(nums[--right],nums[i]);}}}};复杂度分析时间复杂度O ( n ) O(n)O(n)仅遍历一次数组每个元素最多被交换一次。空间复杂度O ( 1 ) O(1)O(1)仅用三个指针原地排序。二、912. 排序数组中等题目描述给你一个整数数组nums请你将该数组升序排列。你必须在不使用任何内置函数的情况下解决问题时间复杂度为O ( n log ⁡ n ) O(n \log n)O(nlogn)并且空间复杂度尽可能小。示例1输入nums [5,2,3,1] 输出[1,2,3,5]示例2输入nums [5,1,1,2,0,0] 输出[0,0,1,1,2,5]思路分析归并排序归并排序是稳定的O ( n log ⁡ n ) O(n \log n)O(nlogn)排序算法核心是分治思想分将数组从中间不断二分直到每个子数组长度为1天然有序治将两个有序子数组合并为一个有序数组递归回溯合并时用双指针遍历两个子数组按大小顺序放入临时数组最后拷贝回原数组。完整C代码classSolution{public:vectorintsortArray(vectorintrecord){merge(record,0,record.size()-1);returnrecord;}voidmerge(vectorintrecord,intleft,intright){if(leftright)return;intmid(leftright)1;// 递归分治merge(record,left,mid);merge(record,mid1,right);// 合并两个有序子数组vectorinttmp(right-left1);intcur1left,cur2mid1,i0;while(cur1midcur2right){tmp[i]record[cur1]record[cur2]?record[cur1]:record[cur2];}// 拷贝剩余元素while(cur1mid)tmp[i]record[cur1];while(cur2right)tmp[i]record[cur2];// 写回原数组for(intileft;iright;i){record[i]tmp[i-left];}}};复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)二分层数为log ⁡ n \log nlogn每层合并时间为O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)合并时需要临时数组存储中间结果。三、LCR 170. 交易逆序对的总数困难题目描述在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录record返回其中存在的「交易逆序对」总数。示例1输入record [9, 7, 5, 4, 6] 输出8 解释交易中的逆序对为 (9,7), (9,5), (9,4), (9,6), (7,5), (7,4), (7,6), (5,4)。思路分析归并排序求逆序对逆序对的统计是归并排序的经典应用核心是在合并阶段统计逆序对归并排序的分治过程不变在合并两个有序子数组[left, mid]和[mid1, right]时如果record[cur1] record[cur2]说明cur1到mid之间的所有元素都大于record[cur2]逆序对数量 mid - cur1 1否则正常合并递归回溯时累加所有逆序对最终得到总逆序对数量。完整C代码classSolution{public:intreversePairs(vectorintrecord){intres0;merge(record,0,record.size()-1,res);returnres;}voidmerge(vectorintrecord,intleft,intright,intres){if(leftright)return;intmid(leftright)1;merge(record,left,mid,res);merge(record,mid1,right,res);vectorinttmp(right-left1);intcur1left,cur2mid1,i0;while(cur1midcur2right){if(record[cur1]record[cur2]){// 统计逆序对cur1到mid的元素都大于cur2resmid-cur11;tmp[i]record[cur2];}else{tmp[i]record[cur1];}}while(cur1mid)tmp[i]record[cur1];while(cur2right)tmp[i]record[cur2];for(intileft;iright;i){record[i]tmp[i-left];}}};复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)归并排序的时间复杂度统计逆序对仅增加O(1)操作。空间复杂度O ( n ) O(n)O(n)临时数组的空间。四、2. 两数相加中等题目描述给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。示例1输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807思路分析链表模拟加法这道题是链表操作的经典入门题核心是模拟竖式加法定义两个指针cur1、cur2分别遍历两个链表同时维护一个进位变量t初始为0遍历两个链表只要有一个链表不为空或进位不为0就继续计算累加当前节点的值和进位t cur1 ? cur1-val : 0; t cur2 ? cur2-val : 0创建新节点存储t % 10更新进位t / 10指针后移直到两个链表都遍历完且进位为0最后返回虚拟头节点的下一个节点避免处理头节点为空的情况。完整C代码/** * 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) {} * }; */classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){ListNode*cur1l1,*cur2l2;ListNode*newnodenewListNode(0);// 虚拟头节点ListNode*prevnewnode;intt0;// 进位while(cur1||cur2||t){if(cur1){tcur1-val;cur1cur1-next;}if(cur2){tcur2-val;cur2cur2-next;}// 创建新节点prev-nextnewListNode(t%10);prevprev-next;t/10;}ListNode*resnewnode-next;deletenewnode;// 释放虚拟头节点returnres;}};复杂度分析时间复杂度O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))m mm和n nn分别是两个链表的长度最多遍历较长链表一次。空间复杂度O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))结果链表的长度最多为max ⁡ ( m , n ) 1 \max(m, n) 1max(m,n)1进位。五、24. 两两交换链表中的节点中等题目描述给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例1输入head [1,2,3,4] 输出[2,1,4,3]示例2输入head [] 输出[]示例3输入head [1] 输出[1]思路分析链表指针操作这道题考察链表的指针操作核心是用虚拟头节点简化头节点交换的逻辑创建虚拟头节点newhead指向原链表头节点避免处理头节点为空的特殊情况定义三个指针prev当前交换组的前一个节点、cur交换组的第一个节点、next交换组的第二个节点、nnext下一个交换组的第一个节点循环交换prev-next next前一个节点指向交换后的第一个节点next-next cur交换两个节点cur-next nnext交换后的第二个节点指向下一个交换组更新指针prev curcur nnext继续下一组交换最后返回虚拟头节点的下一个节点释放虚拟头节点避免内存泄漏。完整C代码/** * 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) {} * }; */classSolution{public:ListNode*swapPairs(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;ListNode*newheadnewListNode(0);newhead-nexthead;ListNode*prevnewhead,*curprev-next,*nextcur-next,*nnextnext-next;while(curnext){// 交换节点prev-nextnext;next-nextcur;cur-nextnnext;// 更新指针prevcur;curnnext;if(cur)nextcur-next;if(next)nnextnext-next;}ListNode*resnewhead-next;deletenewhead;returnres;}};复杂度分析时间复杂度O ( n ) O(n)O(n)仅遍历一次链表每个节点最多被访问一次。空间复杂度O ( 1 ) O(1)O(1)仅用几个指针原地操作。六、算法核心总结1. 排序算法对比算法时间复杂度空间复杂度稳定性适用场景三指针法荷兰国旗O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)稳定仅0/1/2三种元素的排序归并排序O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n ) O(n)O(n)稳定通用排序适合链表排序归并求逆序对O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n ) O(n)O(n)稳定统计数组逆序对2. 链表操作核心技巧虚拟头节点统一处理头节点交换、插入、删除等操作避免特殊情况指针备份修改指针前先备份后续节点避免链表断裂边界处理始终考虑链表为空、长度为1、最后一组交换等边界情况面试高频追问颜色分类除了三指针还有其他解法吗可以用两次遍历第一次统计0、1、2的数量第二次按数量重写数组时间复杂度O(n)空间复杂度O(1)但三指针法是原地一次遍历更优。归并排序可以优化空间吗可以用「原地归并排序」但时间复杂度会退化到O ( n 2 ) O(n^2)O(n2)工程中一般用临时数组的归并排序空间换时间。两数相加如果链表是正序存储怎么办可以先反转链表再按本题逻辑相加最后反转结果或者用栈存储链表元素再出栈相加。两两交换链表节点可以用递归吗可以递归逻辑交换前两个节点递归处理后续链表时间复杂度O(n)空间复杂度O(n)递归栈迭代法空间更优。