交换链表中的节点 图解题解
这道题到底在问什么
- 输入
- head=[1,2,3,4,5], k=2
- 输出
- [1,4,3,2,5]
- 输入
- head=[1], k=1
- 输出
- [1]
最优解：一步一步想明白
- 3记住「first 先走 k-1 步定位正数第 k,再用同步双指针把 second 推到倒数第 k」,下面逐帧套它。
- 4先看整条链表 1→2→3→4→5→6→7,k=3。目标:找到正数第 3 个和倒数第 3 个,交换它们的值。从左往右数第 3 个是节点 3,从右往左数第 3 个是节点 5。
- 5first 指针从头节点 1 出发。要走 k-1=2 步才能到正数第 3 个(头节点本身算第 1 个,所以走 k-1 步,不是 k 步)。
- 6看 first 的下一个节点 2,准备往后挪一格。
- 7第 1 步落位:first 到节点 2。还差一步。
- 8看 first 的下一个节点 3,准备往后挪一格。
- 9第 2 步落位:first 到节点 3。走满 k-1=2 步,first 就停在正数第 3 个节点 3 上,锁定它。
- 10first 已锁定正数第 3 个节点(值 3,蓝色)。接下来要靠它找出倒数第 3 个。
- 11现在 fast 从 first(节点 3)出发、second 从 head(节点 1)出发,两者相隔 k-1=2 格。只要让它俩同步往后走,等 fast 走到链尾,second 与链尾的距离也正好是 k-1,就停在倒数第 3 个上。
- 12fast.next 存在(指向节点 4),说明 fast 还没到尾,两个指针一起往后走一格。
- 13走一步:fast 到节点 4,second 到节点 2。
- 14fast.next 存在(指向节点 5),说明 fast 还没到尾,两个指针一起往后走一格。
- 15走一步:fast 到节点 5,second 到节点 3。
- 16fast.next 存在(指向节点 6),说明 fast 还没到尾,两个指针一起往后走一格。
- 17走一步:fast 到节点 6,second 到节点 4。
- 18fast.next 存在(指向节点 7),说明 fast 还没到尾,两个指针一起往后走一格。
- 19走一步:fast 到节点 7,已是链尾(fast.next 为空),循环停下。此刻 second 停在节点 5。
- 20fast 已在链尾、second 与链尾正好相隔 k-1=2 格,所以 second 就是倒数第 3 个节点(值 5)。两个目标都定位好了。
- 21开始交换:正数第 3 个是 3、倒数第 3 个是 5。下面只换这两个节点的值,不动任何指针。
- 22交换第一步:用一个临时变量存住 first 的值 3,免得马上被覆盖。
- 23交换第二步:把 second 的值 5 写进 first 的位置,first 这个节点现在显示 5。
- 24交换第三步:把暂存的 3 写进 second 的位置。两个值就互换好了。
- 25交换完成:链表变成 1,2,5,4,3,6,7。回头看,我们只用一趟双指针定位了正数第 k 和倒数第 k,再换两个值就收工,全程 O(1) 额外空间、一根指针没改。
⚠️ 容易写错的地方
✗ 错：交换节点指针(易错且没必要)
✓ 对：直接交换两个节点的值
本题只要求结果链表正确,换值 O(1) 最简单;换节点要处理前驱、相邻、头节点多种情形
✗ 错：first 走了 k 步
✓ 对：first 只走 k-1 步
头节点算第 1 个,从 head 走 k-1 步才到正数第 k 个
✗ 错：同步走写成 while fast 非空
✓ 对：while fast.next 非空(到最后一个节点就停)
写成 fast 非空会让 second 多走一格、落到倒数第 k-1 个
完整代码（Python / C++ / Java）
Python
from typing import Optional, List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
first = head
for _ in range(k - 1):
first = first.next
fast = first
second = head
while fast.next:
fast = fast.next
second = second.next
first.val, second.val = second.val, first.val
return headC++
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
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) {}
};
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode* first = head;
for (int i = 1; i < k; ++i) first = first->next;
ListNode* fast = first;
ListNode* second = head;
while (fast->next) { fast = fast->next; second = second->next; }
swap(first->val, second->val);
return head;
}
};Java
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode first = head;
for (int i = 1; i < k; i++) first = first.next;
ListNode fast = first, second = head;
while (fast.next != null) {
fast = fast.next;
second = second.next;
}
int t = first.val; first.val = second.val; second.val = t;
return head;
}
}复杂度
时间
O(n)
first 走 k-1 步、再同步走到链尾,合起来不超过遍历整条链一遍多一点,n 是链表长度
空间
O(1)
只用 first、fast、second 几个指针和一个临时变量,不开额外结构
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 交换链表中的节点 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么交换值而不是交换节点?+
题目只看结果链表对不对,交换值是 O(1) 的最简做法。交换节点要小心处理两节点的前驱、是否相邻、是否为头节点等多种情形,代码长且易错。面试里可以主动说明:除非面试官明确要求交换节点本身,否则换值最干净。
能只遍历一趟吗?+
可以。先让 first 走 k-1 步定位正数第 k(这是一段线性);再让 fast 从 first、second 从 head 同步走到 fast 到链尾(又一段线性)。全程不需要先求链表长度,属于一次遍历的范畴,时间 O(n)、空间 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 交换链表中的节点 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。