两两交换链表中的节点：链表基础与递归思路详解

1. 引言在 LeetCode 的经典题目中「两两交换链表中的节点」Swap Nodes in Pairs是一道非常能考察链表基本功和递归思维的题目。很多初学者在面对这道题时往往会被指针的来回指向绕晕。本文将从链表的基本知识讲起逐步深入到递归方法的基本思路最后给出完整的代码实现帮助你彻底吃透这道题。2. 链表的基本知识2.1 什么是链表链表Linked List是一种线性数据结构它通过「指针」将一系列节点串联起来。与数组不同链表在内存中并不需要连续的空间每个节点除了存储自身的数据val之外还要存储指向下一个节点的指针next。publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}2.2 链表的核心特点非连续存储节点在内存中分散存放通过指针连接。动态大小链表可以随时增删节点不需要像数组那样预先分配固定容量。插入/删除高效在已知前驱节点的情况下插入和删除操作的时间复杂度为 O(1)。随机访问低效要访问第 k 个节点必须从头节点开始逐个遍历时间复杂度为 O(n)。2.3 链表的遍历链表的遍历非常简单核心就是不断移动cur指针ListNodecurhead;while(cur!null){// 处理当前节点System.out.println(cur.val);// 移动到下一个节点curcur.next;}2.4 为什么链表题容易出错链表题出错的高频原因主要有两个指针丢失修改next指向时如果没有先用临时变量保存原指针就会导致后续节点无法访问。边界条件空链表head null、只有一个节点head.next null等特殊情况没有处理好。3. 题目理解两两交换链表中的节点3.1 题目描述给定一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例输入head [1,2,3,4]输出[2,1,4,3]3.2 题目要点两两一组进行交换即第 1 个和第 2 个交换第 3 个和第 4 个交换以此类推。如果链表长度是奇数最后一个节点保持不动。只能交换节点本身不能只交换节点里的值。4. 递归方法的基本思路4.1 什么是递归递归Recursion是一种通过「函数调用自身」来解决问题的方法。一个递归问题通常包含两个核心要素递归基Base Case问题规模最小、可以直接返回答案的情况用于终止递归。递归关系Recursive Relation把大问题拆解成规模更小的同类子问题并建立它们之间的联系。4.2 递归的思考方式面对递归问题不要试图在脑子里把每一层调用都展开。正确的思考方式是假设子问题已经解决相信递归函数能正确处理规模更小的子问题。只关心当前层要做什么当前层只需要处理「本层」的逻辑剩下的交给递归。4.3 用递归思考「两两交换」我们以链表1 - 2 - 3 - 4为例思考如何用递归解决第一步找递归基如果链表为空head null或者只有一个节点head.next null无法进行交换直接返回head。第二步拆解子问题对于链表1 - 2 - 3 - 4我们先把前两个节点1和2拿出来。剩下的链表3 - 4是一个规模更小的同类问题我们相信递归函数swapPairs(3)能把它正确交换成4 - 3。第三步处理当前层当前层要做的就是把1和2交换位置并把交换后的结果与子问题的结果连接起来2.next 11.next swapPairs(3)即4 - 3最终得到2 - 1 - 4 - 3。4.4 递归代码实现publicListNodeswapPairs(ListNodehead){// 递归基空链表或只有一个节点无法交换if(headnull||head.nextnull){returnhead;}// 保存第二个节点ListNodenewHeadhead.next;// 递归处理剩余部分head.next 指向交换后的子链表head.nextswapPairs(newHead.next);// 第二个节点指向第一个节点完成交换newHead.nexthead;// 返回新的头节点returnnewHead;}4.5 递归过程图解swapPairs(1-2-3-4)newHead 2head.next swapPairs(3-4)swapPairs(3-4) 返回 4-3head.next 4-3newHead.next head返回 2-1-4-34.6 时间复杂度与空间复杂度时间复杂度O(n)每个节点只被访问一次。空间复杂度O(n)递归调用栈的深度为 n/2即 O(n)。5. 迭代方法补充除了递归这道题也可以用迭代的方式解决通过引入一个虚拟头节点dummy node来简化边界处理publicListNodeswapPairs(ListNodehead){ListNodedummynewListNode(0);dummy.nexthead;ListNodeprevdummy;while(prev.next!nullprev.next.next!null){ListNodefirstprev.next;ListNodesecondfirst.next;// 交换两个节点first.nextsecond.next;second.nextfirst;prev.nextsecond;// 移动 prev 到下一组的前驱prevfirst;}returndummy.next;}迭代方法的时间复杂度同样是 O(n)但空间复杂度优化到了 O(1)。6. 总结「两两交换链表中的节点」是一道非常经典的链表递归题。通过这道题我们重点掌握了链表的基本结构节点由val和next组成遍历靠移动指针。递归的核心思路先找递归基再拆解子问题最后处理当前层。递归代码的写法相信子问题已解决只关心当前层的指针调整。建议读者在理解递归思路后再动手实现一遍迭代版本对比两种方法的异同这样对链表的理解会更加深刻。