1721.交换链表中的节点
题目描述
原题
给你链表的头节点 head
和一个整数 k
。
交换 链表正数第 k
个节点和倒数第 k
个节点的值后,返回链表的头节点(链表 从 1 开始索引)。
示例 1:
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/10/linked1.jpg)
| 输入: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
题解
| /**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapNodes(ListNode head, int k) {
//fast先走k步获取第k个
//创建slow两个一起走 fast为null时slow就等于倒数第k个
//然后就行交换
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode fast = dummyNode;
for(int i = 0;i < k && fast!=null ;i++){
fast = fast.next;
}
ListNode firstK = fast;
ListNode slow = dummyNode;
while(fast!=null){
fast = fast.next;
slow = slow.next;
}
ListNode lastK = slow;
//判断两个值是否相等 不相等就就进行交换
if(firstK.val != lastK.val){
int temp = firstK.val;
firstK.val = lastK.val;
lastK.val = temp;
}
return dummyNode.next;
}
}
|