LeetCode 题解工作台
交换链表中的节点
给你链表的头节点 head 和一个整数 k 。 交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引 ）。 示例 1： 输入： head = [1,2,3,4,5], k = 2 输出： [1,4,3,2,5] 示例 2： 输入： head = [7,9,…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们可以先用快指针 找到链表的第 个节点，用指针 指向它。然后我们再用慢指针 从链表的头节点出发，快慢指针同时向后移动，当快指针到达链表的最后一个节点时，慢指针 恰好指向倒数第 个节点，用指针 指向它。此时，我们只需要交换 和 的值即可。 时间复杂度 ，其中 是链表的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你链表的头节点 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
解题思路
方法一：快慢指针
我们可以先用快指针 找到链表的第 个节点，用指针 指向它。然后我们再用慢指针 从链表的头节点出发，快慢指针同时向后移动，当快指针到达链表的最后一个节点时，慢指针 恰好指向倒数第 个节点，用指针 指向它。此时，我们只需要交换 和 的值即可。
时间复杂度 ，其中 是链表的长度。空间复杂度 。
# Definition for singly-linked 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]:
fast = slow = head
for _ in range(k - 1):
fast = fast.next
p = fast
while fast.next:
fast, slow = fast.next, slow.next
q = slow
p.val, q.val = q.val, p.val
return head
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should consider both time and space complexity when discussing their approach.
- question_mark
Look for an understanding of two-pointer techniques and linked-list manipulation.
- question_mark
Candidates should be able to explain how they can optimize the problem by avoiding unnecessary space usage.
常见陷阱
外企场景- error
Failing to handle edge cases such as when k is exactly at the middle of the list or when the list has only one node.
- error
Using extra space unnecessarily when an in-place solution is possible.
- error
Not correctly identifying the kth node from the end by failing to account for list length or pointer alignment.
进阶变体
外企场景- arrow_right_alt
What if the linked list is circular? How would the approach change?
- arrow_right_alt
Modify the problem to swap multiple nodes, not just the kth node from the start and end.
- arrow_right_alt
Optimize the problem to work with doubly linked lists.