题目描述
给定链表的头节点 head
和一个整数 k
。
交换 链表正数第 k
个节点和倒数第 k
个节点的值后,返回链表的头节点(链表 从 1
开始索引)。
样例
输入:head = [1,2,3,4,5], k = 2
输出:[1,4,3,2,5]
输入:head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出:[7,9,6,6,8,7,3,0,9,5]
输入:head = [1], k = 1
输出:[1]
输入:head = [1,2], k = 1
输出:[2,1]
输入:head = [1,2,3], k = 2
输出:[1,2,3]
限制
- 链表中节点的数目是
n
。 1 <= k <= n <= 10^5
0 <= Node.val <= 100
算法1
(三次遍历) $O(n)$
- 先遍历一次求出链表的长度
n
。 - 然后分别找到第
k
个节点和第n - k + 1
个节点,并交换其值。
时间复杂度
- 遍历链表三次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
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 {
private:
ListNode* find(ListNode *head, int k) {
int i = 1;
for (ListNode *p = head; p != nullptr; p = p->next, i++)
if (i == k)
return p;
return nullptr;
}
public:
ListNode* swapNodes(ListNode* head, int k) {
int n = 0;
for (ListNode *p = head; p != nullptr; p = p->next)
n++;
ListNode *p = find(head, k);
ListNode *q = find(head, n - k + 1);
swap(p->val, q->val);
return head;
}
};
算法2
(两次遍历) $O(n)$
- 先找到第 $k$ 个节点 $p$。
- 此时 $p$ 后还有 $n - k$ 个节点。记录 $p$ 的一个副本 $pc$。
- 令 $pc$ 和 $q$ 同时移动,直到 $pc->next$ 为空。
- 此时 $p$ 是第 $k$ 个节点,$q$ 是倒数第 $k$ 个节点。
时间复杂度
- 遍历链表两次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
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 *p = head;
while (--k) p = p->next;
ListNode *pc = p, *q = head;
while (pc->next) {
q = q->next;
pc = pc->next;
}
swap(p->val, q->val);
return head;
}
};
按道理面试时候不能交换节点值吧,应该交换节点的地址吧
交换节点的one-pass,类似链表找环,快慢指针
如果面试讨论能不能交换值这么无聊的问题,我宁愿不去这个公司
😂
Nice正规做法强啊