Leetcode 108 交换链表中的节点

 1 题目

1721. 交换链表中的节点

给你链表的头节点 head 和一个整数 k 。

交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

示例 1：

输入：head = [1,2,3,4,5], k = 2 输出：[1,4,3,2,5]

示例 2：

输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5 输出：[7,9,6,6,8,7,3,0,9,5]

示例 3：

输入：head = [1], k = 1 输出：[1]

示例 4：

输入：head = [1,2], k = 1 输出：[2,1]

示例 5：

输入：head = [1,2,3], k = 2 输出：[1,2,3]

提示：

• 链表中节点的数目是 n
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

2 代码实现

c++

/** * 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) {} * }; */ class Solution { public: ListNode* swapNodes(ListNode* head, int k) { ListNode* first = head ; for (int i = 1 ; i < k ; ++ i){ first = first -> next ; } ListNode* second = head ; ListNode* fast = first ; while (fast -> next != nullptr){ fast = fast -> next ; second = second -> next ; } swap(second-> val , first->val); return head ; } }; 

js

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var swapNodes = function(head, k) { let first = head ; for (let i = 1 ; i < k ;++i){ first = first.next; } let second = head ; let fast = first ; while(fast.next){ fast = fast.next ; second=second.next; } const temp = first.val ; first.val = second.val ; second.val = temp ; return head ; };

注意js里面没有内置的swap函数！！！自己实现一下值的交换！！

思考

真的很直接的思路了，但是链表结点的操作顺序要小心，然后正数、 倒数实在是太直白了，正数不用说，倒数就是一个间隔k的前后指针就ok了。自己理一理思路试着写一下，思路很简单，难的地方是操作顺序和各种循环细节。要防止链表结点丢失。

题解

解题思路（贴合你的思考）

1. 定位正数第 k 个节点：从头节点出发，移动 k-1 步，直接找到目标节点，这一步逻辑直白，只需注意循环次数。
2. 定位倒数第 k 个节点：用 “前后指针（快慢指针）” 实现 —— 先让快指针走 k 步，再让快慢指针同步走，快指针到末尾时，慢指针就是倒数第 k 个节点，核心是利用 “间隔 k” 的特性，避免先遍历统计长度的二次遍历。
3. 交换值而非节点：仅交换两个节点的 val，不修改链表的 next 指针，彻底避免节点丢失的问题，这是最简洁且安全的操作方式。

C++ 核心代码

/** * 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) {} * }; */ class Solution { public: ListNode* swapNodes(ListNode* head, int k) { // 1. 找到正数第k个节点（注意从1开始索引） ListNode* first = head; for (int i = 0; i < k - 1; ++i) { first = first->next; // 移动k-1步，定位正数第k个节点 } // 2. 找到倒数第k个节点（前后指针法，避免节点丢失） ListNode* second = head; ListNode* fast = first; // 快指针先站在正数第k个节点，形成k步间隔 while (fast->next != nullptr) { // 快指针走到末尾时，慢指针就是倒数第k个 fast = fast->next; second = second->next; } // 3. 仅交换两个节点的值，无需修改链表结构，避免节点丢失 swap(first->val, second->val); // 返回原链表头节点 return head; } }; 

代码关键解释（贴合你的思考重点）

1. 正数第 k 个节点定位：
   • 循环 k-1 次而非 k 次，因为链表从 1 开始索引，初始的 first = head 已经是第 1 个节点，移动 k-1 步正好到第 k 个，这是容易出错的细节，需注意循环次数。
2. 倒数第 k 个节点定位：
   • 快指针 fast 直接从正数第 k 个节点起步，和慢指针 second（初始在头节点）形成 k 步的间隔，之后同步移动，直到快指针到链表末尾（fast->next == nullptr），此时慢指针恰好指向倒数第 k 个节点。
   • 这种方式只需一次遍历，且全程只操作指针移动，不会出现节点丢失的问题，符合你 “小心操作顺序、防止链表结点丢失” 的思考。
3. 交换逻辑：
   • 直接用 C++ 内置的 swap 函数交换两个节点的 val，无需修改 next 指针，是最安全的方式，彻底规避了链表节点操作中 “断链、丢节点” 的风险。

测试验证（力扣提交场景）

总结

1. 核心逻辑：先精准定位两个目标节点，仅交换值而非节点，避免链表结构修改带来的节点丢失问题。
2. 关键技巧：用间隔 k 的快慢指针一次遍历找到倒数第 k 个节点，时间复杂度 O (n)，空间复杂度 O (1)，符合高效要求。
3. 细节注意：循环次数为 k-1 而非 k，快慢指针同步移动的终止条件是 fast->next == nullptr，这些细节保证了定位的准确性。

诶，原来直接交换这两个节点的val是可以的吗！？

自己乱写

/** * 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) {} * }; */ class Solution { public: ListNode* swapNodes(ListNode* head, int k) { ListNode* first = head ; for (int i = 1 ; i < k ; ++ i){ first = first -> next ; } ListNode* second = head ; ListNode* fast = head ; while (fast -> next != nullptr){ fast = fast -> next ; second = second -> next ; } swap(second-> val , first->val); return head ; } }; 

解答错误！！！！

啊，我发现了，fast要先站在first的地方，形成k个间隔啊！

3 小结

自己多写写，多练，注意js里面的api，熟悉起来js的语法！！！

踩坑