交换链表中的节点
难度:
标签:
题目描述
给你链表的头节点 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 <= 1050 <= Node.val <= 100
代码结果
运行时间: 892 ms, 内存: 48.6 MB
/*
* 思路：
* 1. 使用流收集所有节点的引用。
* 2. 交换第 k 个节点和倒数第 k 个节点的值。
* 3. 返回修改后的链表头节点。
*/
import java.util.*;
import java.util.stream.*;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode swapNodes(ListNode head, int k) {
List<ListNode> nodes = new ArrayList<>();
ListNode current = head;
// 收集所有节点
while (current != null) {
nodes.add(current);
current = current.next;
}
// 交换第 k 个节点和倒数第 k 个节点的值
int tmp = nodes.get(k - 1).val;
nodes.get(k - 1).val = nodes.get(nodes.size() - k).val;
nodes.get(nodes.size() - k).val = tmp;
return head;
}
}
解释
方法:
这个题解的思路是先找到正数第k个节点，用指针p记录其位置。然后用快慢指针f和s同时从头节点出发，f先走k步，接着f和s同时向后移动，直到f走到链表末尾。此时s指向倒数第k个节点。最后交换p和s指向的节点的值即可。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在链表为单节点时（如示例3中head = [1]），交换操作实际上有什么效果吗？
▷🦆
如果链表的长度正好是2k，那么正数第k个节点和倒数第k个节点是否指向同一个节点？这种情况下算法如何处理？
▷🦆
您提到的算法中，快指针f先走k-1步，然后再走一步开始和慢指针s一起移动。这样设计的原因是什么？是否可以在开始时就让f和s一起走？
▷🦆
您提到交换的是节点的值，这种方式与交换节点本身相比有什么优势或劣势？
▷