文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析思路1迭代法思路2递归法2、解题代码思路1迭代法思路2递归法三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接24.两两交换链表中的节点2、题目描述二、个人思路整理1、思路分析参考【图解】迭代/递归一张图秒懂Python/Java/C/C/Go/JS辅助理解。思路1迭代法核心思路引入虚拟头节点dummy统一头节点的交换逻辑使用指针 cur 始终指向待交换节点对的前驱节点。具体步骤循环条件为后面至少有两个节点cur-next ! nullptr cur-next-next ! nullptr。记待交换的两个节点为node1 cur-next、node2 cur-next-next记录后续链表起点node3 node2-next。执行三步指针重定向cur-next node2前驱指向第 2 个节点node2-next node1第 2 个节点指向第 1 个节点node1-next node3第 1 个节点接上后续链表移动指针cur node1进入下一组交换。思路2递归法核心思路将原问题拆解为“交换当前前两个节点”与“递归处理剩余子链表”。具体步骤终止条件当前无节点head nullptr或只剩单节点head-next nullptr时无法配对直接返回head。单层交换与链接设待交换的第二个节点为nextNode head-next。将剩余子链表交由递归处理并让当前第 1 个节点指向其返回的新头节点head-next swapPairs(nextNode-next)。将当前第 2 个节点指向第 1 个节点完成组内反转nextNode-next head。返回值返回本组交换后的新头节点nextNode。2、解题代码思路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) {} * }; */classSolution{public:ListNode*swapPairs(ListNode*head){// 创建哨兵/虚拟头节点简化头节点的交换逻辑ListNodedummy(0,head);// cur指向待交换的两个节点的前驱节点ListNode*curdummy;// 只有当后面至少存在两个节点时才需要进行交换while(cur-next!nullptrcur-next-next!nullptr){// 记录待操作的三个关键节点ListNode*node1cur-next;// 第1个节点ListNode*node2cur-next-next;//第2个节点ListNode*node3node2-next;//下一组的起始节点// 交换指针cur-nextnode2;// 1. 前驱指向第 2 个节点cur-2node2-nextnode1;// 2. 第 2 个节点指向第 1 个节点2-1node1-nextnode3;// 3. 第 1 个节点指向下一组头部1-3// cur 移动到交换后的末尾即原node1准备处理下一对curnode1;}// 返回新链表的真实头节点returndummy.next;}};复杂度分析时间复杂度O ( n ) O(n)O(n)仅需遍历一次链表。空间复杂度O ( 1 ) O(1)O(1)仅使用常数个辅助指针变量。思路2递归法/** * 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*nextNodehead-next;ListNode*nextPairnextNode-next;// 递归处理后续剩余链表并将当前第一节点的next指向其返回的新头节点head-nextswapPairs(nextPair);// 将当前第二节点的next指向当前第一节点完成本组反转nextNode-nexthead;// 返回交换后的新头节点即原第二节点returnnextNode;}};复杂度分析时间复杂度O ( n ) O(n)O(n)每个节点被访问一次。空间复杂度O ( n ) O(n)O(n)取决于递归调用栈的深度最大深度为n / 2 n / 2n/2。三、知识风暴虚拟头节点 指针重定向是本题的核心思想引入哨兵节点dummy统一头节点的交换逻辑通过三步指针重定向完成相邻两节点的交换再移动指针进入下一组一次遍历即可完成全部交换。算法核心思想虚拟头节点dummy-next head统一处理头节点交换的边界情况避免单独写if判断。三步重定向cur-next node2、node2-next node1、node1-next node3完成一组相邻节点的交换。循环推进cur node1让cur始终指向待交换节点对的前驱进入下一组。一次遍历整个过程只需遍历链表一次时间复杂度为O ( n ) O(n)O(n)。常见对比迭代法 vs 递归法方法核心思路时间复杂度空间复杂度适用场景迭代法虚拟头节点 三步指针重定向循环交换O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)本题标准解法面试最常考察无栈溢出风险递归法拆解为“交换前两个节点 递归处理剩余子链表”O ( n ) O(n)O(n)O ( n ) O(n)O(n)递归栈代码简洁优雅但链表较长时可能栈溢出使用要点虚拟头节点dummy-next head统一处理头节点交换的边界情况代码更简洁。循环条件while (cur-next ! nullptr cur-next-next ! nullptr)保证后面至少有两个节点才交换。记录后续节点交换前先记录node3 node2-next防止指针重定向后丢失后续链表。指针移动交换完成后cur node1此时node1已位于本组末尾恰好作为下一组的前驱。递归终止条件head nullptr || head-next nullptr当前无节点或只剩单节点时无法配对直接返回。算法变体与扩展反转链表cur指向当前节点通过nextTemp暂存后继逐个反转指针方向对应 LeetCode 206。K 个一组翻转链表在本题两两交换的基础上推广先统计剩余节点数是否满 K 个再分段反转对应 LeetCode 25。重排链表结合快慢指针找中点 反转后半段 交替合并实现O ( 1 ) O(1)O(1)空间的重排对应 LeetCode 143。旋转链表先求链表长度并成环再定位新头节点断开实现整体右移 K 位对应 LeetCode 61。与其他算法的对比迭代法O ( n ) O(n)O(n)时间、O ( 1 ) O(1)O(1)空间一次遍历即可完成交换是本题最优解。递归法代码优雅、逻辑清晰但递归深度等于链表长度的一半长链表下可能栈溢出不具实用性。相关 LeetCode 例题24. 两两交换链表中的节点本题虚拟头节点 指针重定向206. 反转链表指针逐个反转25. K 个一组翻转链表两两交换的推广143. 重排链表快慢指针 反转 合并