交换链表中的节点（1721）

题目

给你链表的头节点 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 <= 105
• 0 <= Node.val <= 100

算法

数组

将链表转换为数组，然后交换数组中的两个值，然后再将数组转化为链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const swapNodes = (head, k) => {
	const arr = [];
	while (head) {
		arr.push(head.val);
		head = head.next;
	}
	let num1 = arr[k - 1],
		num2 = arr[arr.length - k];
	arr[k - 1] = num2;
	arr[arr.length - k] = num1;
	let sentinel = new ListNode();
	let node = sentinel;
	while (arr.length) {
		let num = arr.shift();
		node.next = new ListNode(num);
		node = node.next;
	}
	return sentinel.next;
};

快慢指针

建立快指针fast和慢指针slow，快指针fast先走k-1步，此时fast指向要交换的第一个值；然后快慢指针同时向后移动，当fast指向最后一个节点的时候，slow指向第二个要交换的值

交换两个节点，我们可以变相的交换这两个节点的值val

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const swapNodes = (head, k) => {
	let fast = head,
		slow = head;
	let temp;
	while (k > 1) {
		fast = fast.next;
		k--;
	}
	temp = fast;
	while (fast.next) {
		slow = slow.next;
		fast = fast.next;
	}
	const swapVal = slow.val;
	slow.val = temp.val;
	temp.val = swapVal;
	return head;
};