题目

标题和出处

标题：交换链表中的结点

出处：1721. 交换链表中的结点

难度

3 级

题目描述

要求

给你链表的头结点 $\text{head}$ 和一个整数 $\text{k}$。

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

示例

示例 1：

输入：$\text{head = [1,2,3,4,5], k = 2}$
输出：$\text{[1,4,3,2,5]}$

示例 2：

输入：$\text{head = [7,9,6,6,7,8,3,0,9,5], k = 5}$
输出：$\text{[7,9,6,6,8,7,3,0,9,5]}$

示例 3：

输入：$\text{head = [1], k = 1}$
输出：$\text{[1]}$

示例 4：

输入：$\text{head = [1,2], k = 1}$
输出：$\text{[2,1]}$

示例 5：

输入：$\text{head = [1,2,3], k = 2}$
输出：$\text{[1,2,3]}$

数据范围

• 链表中结点的数目是 $\text{n}$
• $\text{1}\le \text{k}\le \text{n}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{Node.val}\le \text{100}$

前言

对于有 $n$ 个结点的链表，倒数第 $k$ 个结点为正数第 $n-k+1$ 个结点。定位到链表的第 $k$ 个结点和第 $n-k+1$ 个结点之后，将这两个结点的值交换即可。

定位到链表的倒数第 $k$ 个结点有两种做法。第一种做法是首先遍历链表得到链表的结点数量 $n$，然后再次遍历链表定位到链表的第 $n-k+1$ 个结点；第二种做法是使用两个指针一次遍历定位到链表的倒数第 $k$ 个结点。

解法一

思路和算法

首先遍历链表得到链表的结点数量 $n$，然后再次遍历链表，分别定位到链表的第 $k$ 个结点和第 $n-k+1$ 个结点。从 $\text{head}$ 出发，分别向后移动 $k-1$ 次和 $n-k$ 次，即可定位到链表的第 $k$ 个结点和第 $n-k+1$ 个结点。

定位到链表的第 $k$ 个结点和第 $n-k+1$ 个结点之后，交换两个结点的值即可。

下图为示例 1 的交换结点的过程。此时 $n=5$，$k=2$，因此定位到第 $2$ 个结点和第 $4$ 个结点，然后交换两个结点的值。

代码

class Solution {public ListNode swapNodes(ListNode head, int k) {int n = 0;ListNode temp = head;while (temp != null) {n++;temp = temp.next;}ListNode node1 = head, node2 = head;for (int i = 1; i < k; i++) {node1 = node1.next;}for (int i = 1; i < n - k + 1; i++) {node2 = node2.next;}int val1 = node1.val, val2 = node2.val;node1.val = val2;node2.val = val1;return head;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。需要遍历链表一次得到链表的结点数量，然后遍历链表分别定位到链表的第 $k$ 个结点和第 $n-k+1$ 个结点。

• 空间复杂度：$O(1)$。

解法二

思路和算法

上述解法需要首先遍历一次链表得到链表的结点数量 $n$。其实，链表的结点数量 $n$ 不需要事先知道。

用 ${\text{node}}_1$ 和 ${\text{node}}_2$ 分别表示链表的正数第 $k$ 个结点和倒数第 $k$ 个结点。从 $\text{head}$ 出发向后移动 $k-1$ 次，即可定位到 ${\text{node}}_1$。对于 ${\text{node}}_2$ 的定位，可以使用两个指针，这两个指针指向的结点在链表中相差 $k$ 个位置。

定位 ${\text{node}}_2$ 时，需要创建临时指针 $\text{temp}$，满足 $\text{temp}$ 在 ${\text{node}}_2$ 的后面 $k$ 个位置。将 ${\text{node}}_2$ 初始化为 $\text{head}$，由于 ${\text{node}}_1$ 在 $\text{head}$ 的后面 $k-1$ 个位置，因此将 $\text{temp}$ 初始化为指向 ${\text{node}}_1$ 的后一个结点，即满足 $\text{temp}$ 在 ${\text{node}}_2$ 的后面 $k$ 个位置；

在初始化 ${\text{node}}_2$ 和 $\text{temp}$ 之后，将 ${\text{node}}_2$ 和 $\text{temp}$ 同时向后移动，直到 $\text{temp}$ 指向 $\text{null}$，此时 ${\text{node}}_2$ 即为链表的倒数第 $k$ 个结点。

定位到链表的正数第 $k$ 个结点和倒数第 $k$ 个结点之后，交换两个结点的值即可。

下图为示例 1 的交换结点的过程。此时 $k=2$，因此 $\text{temp}$ 在 ${\text{node}}_2$ 后面 $2$ 个位置。同时向后移动 ${\text{node}}_2$ 和 $\text{temp}$，直到 $\text{temp}$ 指向 $\text{null}$，${\text{node}}_2$ 为链表的倒数第 $2$ 个结点，然后交换 ${\text{node}}_1$ 和 ${\text{node}}_2$ 的值。

代码

class Solution {public ListNode swapNodes(ListNode head, int k) {ListNode node1 = head;for (int i = 1; i < k; i++) {node1 = node1.next;}ListNode node2 = head, temp = node1.next;while (temp != null) {node2 = node2.next;temp = temp.next;}int val1 = node1.val, val2 = node2.val;node1.val = val2;node2.val = val1;return head;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。需要遍历链表分别定位到链表的正数第 $k$ 个结点和倒数第 $k$ 个结点。

• 空间复杂度：$O(1)$。