两两交换链表中的节点：链表基础与递归思路详解-开发者社区

1. 引言

在 LeetCode 的经典题目中，「两两交换链表中的节点」（Swap Nodes in Pairs）是一道非常能考察链表基本功和递归思维的题目。很多初学者在面对这道题时，往往会被指针的来回指向绕晕。本文将从链表的基本知识讲起，逐步深入到递归方法的基本思路，最后给出完整的代码实现，帮助你彻底吃透这道题。

2. 链表的基本知识

2.1 什么是链表

链表（Linked List）是一种线性数据结构，它通过「指针」将一系列节点串联起来。与数组不同，链表在内存中并不需要连续的空间，每个节点除了存储自身的数据（val）之外，还要存储指向下一个节点的指针（next）。

publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}

2.2 链表的核心特点

非连续存储：节点在内存中分散存放，通过指针连接。
动态大小：链表可以随时增删节点，不需要像数组那样预先分配固定容量。
插入/删除高效：在已知前驱节点的情况下，插入和删除操作的时间复杂度为 O(1)。
随机访问低效：要访问第 k 个节点，必须从头节点开始逐个遍历，时间复杂度为 O(n)。

2.3 链表的遍历

链表的遍历非常简单，核心就是不断移动cur指针：

ListNodecur=head;while(cur!=null){// 处理当前节点System.out.println(cur.val);// 移动到下一个节点cur=cur.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 = 1
- 1.next = swapPairs(3)（即4 -> 3）
最终得到2 -> 1 -> 4 -> 3。

4.4 递归代码实现

publicListNodeswapPairs(ListNodehead){// 递归基：空链表或只有一个节点，无法交换if(head==null||head.next==null){returnhead;}// 保存第二个节点ListNodenewHead=head.next;// 递归处理剩余部分：head.next 指向交换后的子链表head.next=swapPairs(newHead.next);// 第二个节点指向第一个节点，完成交换newHead.next=head;// 返回新的头节点returnnewHead;}

4.5 递归过程图解

4.6 时间复杂度与空间复杂度

时间复杂度：O(n)，每个节点只被访问一次。
空间复杂度：O(n)，递归调用栈的深度为 n/2，即 O(n)。

5. 迭代方法（补充）

除了递归，这道题也可以用迭代的方式解决，通过引入一个虚拟头节点（dummy node）来简化边界处理：

publicListNodeswapPairs(ListNodehead){ListNodedummy=newListNode(0);dummy.next=head;ListNodeprev=dummy;while(prev.next!=null&&prev.next.next!=null){ListNodefirst=prev.next;ListNodesecond=first.next;// 交换两个节点first.next=second.next;second.next=first;prev.next=second;// 移动 prev 到下一组的前驱prev=first;}returndummy.next;}