当前位置：首页 > news >正文

【LeetCode刷题日记：24】两两交换链表

news 2026/6/12 15:09:43

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：今天继续学习链表的相关题目，主要还是考察链表的基本操作，是面试的基础题常考，需要掌握。

题目背景：LeetCode24

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]输出：[2,1,4,3]
示例 2：
输入：head = []输出：[]
示例 3：
输入：head = [1]输出：[1]
提示：
链表中节点的数目在范围[0, 100]内
0 <= Node.val <= 100

题目答案：

第一种解法：

class Solution { public ListNode swapPairs(ListNode head) { ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点 dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作 ListNode cur = dumyhead; ListNode temp; // 临时节点，保存两个节点后面的节点 ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点 ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点 while (cur.next != null && cur.next.next != null) { temp = cur.next.next.next; firstnode = cur.next; secondnode = cur.next.next; cur.next = secondnode; // 步骤一 secondnode.next = firstnode; // 步骤二 firstnode.next = temp; // 步骤三 cur = firstnode; // cur移动，准备下一轮交换 } return dumyhead.next; } }

题目解析：

我们这里仍旧使用虚拟头节点的方式，在做这种题目的时候，我们最好要把流程图画出来，不然容易搞混。

如图所示：我们把虚拟头节点设为cur，然后分别用临时节点保存需要移动的节点，我们这里保存的是第一个和第二个节点，关于temp记录的cur.next.next.next，实际上是为了步骤三交换位置。记录完之后，我们就可以开始交换了

首先cur.next=secondnode,secondnode.next=firstnode;

之后，交换后的firstnode节点的next，实际上就是我们下次开始执行交换的节点的下个节点，也就是我们保存的临时节点temp。

因为是两两交换，自然就是虚拟头节点的next.next.next,这里没什么深究的，而此时的firstnode也就相当于一开始虚拟头节点的作用，用于联系交换后面两个节点。

然后就是关于循环条件

如果链表有偶数个，那么循环的终止条件就是cur.next==null的时候，如图所示，执行完两次交换之后，此时的cur等于被交换之后val==3的那个位置

如图，因为是偶数节点，那么他后面的节点自然就是null

如果是奇数节点，我们画个图理解一下，那么也就是cur节点的next.next节点为null，因为cur.next的节点没有节点与之交换。

注意：这两个条件的位置一定不能交换，否则会报空指针异常

cur.next.next != null // 先执行这个！ // cur.next = 节点1 // cur.next.next = 节点1.next = null // 访问 null.next → 💥 空指针异常！

注意：
其实我们在设置临时节点的时候，只需要保存cur.next和cur.next.next.next,的值，一般不需要设置第二个节点的临时节点去保存值，因为我们拿虚拟节点交换的时候
步骤一：cur.next=cur.next.next（也就是第二个节点变成了第一个节点，交换了位置）
步骤二：firstnode=cur.next.next;（这里如果不用firstnode去记录第一个节点，那么它的值已经在步骤一的时候就被覆盖了）
步骤三：照常

第二种解法：

// 递归版本 class Solution { public ListNode swapPairs(ListNode head) { // base case 退出提交 if(head == null || head.next == null) return head; // 获取当前节点的下一个节点 ListNode next = head.next; // 进行递归 ListNode newNode = swapPairs(next.next); // 这里进行交换 next.next = head; head.next = newNode; return next; } }

题目解析：

其实递归的本质就是代替循环的操作

链表初始状态：
1 → 2 → 3 → 4 → null
第一层调用swapPairs(1)
head = 1，head.next = 2，不为 null，不满足 base case
next = head.next = 2
进入递归newNode = swapPairs(3)（因为next.next = 3）
第二层调用swapPairs(3)
head = 3，head.next = 4，不为 null
next = head.next = 4
进入递归newNode = swapPairs(5)（因为next.next = null）
第三层调用swapPairs(5)
head = null→ 满足 base case，返回null
返回到第二层：newNode = null
回到第二层swapPairs(3)
next = 4，newNode = null
交换操作：
next.next = head→4.next = 3
head.next = newNode→3.next = null
此时链表局部：4 → 3 → null
返回next→ 返回节点 4
状态：第二层返回到第一层的newNode是节点 4，且它带着4 → 3 → null这一段。
回到第一层swapPairs(1)
next = 2，newNode = 4 → 3 → null
交换操作：
next.next = head→2.next = 1
head.next = newNode→1.next = 4
注意此时1.next = 4，所以链表变成：
2 → 1 → 4 → 3 → null
最终返回
next = 2，作为新的头节点返回。
完整结果：2 → 1 → 4 → 3 → null✅
关键点总结：
递归从链表尾部向前建立两两交换后的链表
每次递归返回的是交换完这一对后，这一段的头节点（即原next节点）
newNode接收的是已经交换好的后续部分，然后挂在head.next上