64.反转链表
反转链表
题目
请实现一个函数
reverseLinkedList，该函数接收两个参数： 一个链表的头节点head，表示一个单向链表。 一个整数 k，表示需要反转的子链表的长度。 函数的功能是将链表中每 k 个节点进行反转，如果链表的剩余节点不足 k 个，则不进行反转。最后返回新的头节点。
链表节点定义
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
示例 :
/*
输入：
head：链表的头节点。
k：一个整数，表示每组需要反转的节点数。
输出：
返回一个新的链表头节点，表示反转后的链表。 */
// demo1
// 给定链表 1->2->3->4->5 和 k = 2
// 应返回 2->1->4->5->3
const head1 = new ListNode(
1,
new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))
);
const k1 = 2;
const result1 = reverseLinkedList(head1, k1);
console.log(result1); // 输出：2->1->4->5->3
// demo2
// 给定链表 1->2->3->4->5 和 k = 3
// 应返回 3->2->1->4->5
const head2 = new ListNode(
1,
new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))
);
const k2 = 3;
const result2 = reverseLinkedList(head2, k2);
console.log(result2); // 输出：3->2->1->4->5
要求
TIP
- 请使用 JavaScript 实现该函数。
- 在代码中添加必要的注释，说明关键步骤和逻辑。
- 考虑边界情况，如链表为空、k 大于链表长度等。
参考答案
DETAILS
<script>
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function reverseLinkedList(head, k) {
// 辅助函数：反转链表的前 k 个节点
function reverseKNodes(head, k) {
let current = head;
let prev = null;
let count = 0;
// 反转前 k 个节点
while (current && count < k) {
const nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
count++;
}
// 如果不足 k 个节点，恢复链表
if (count < k) {
current = prev;
prev = null;
while (current) {
const nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return head;
}
// 连接剩余部分
head.next = current;
return prev;
}
// 主函数：处理整个链表
let dummy = new ListNode(0);
dummy.next = head;
let start = dummy;
while (start.next) {
start.next = reverseKNodes(start.next, k);
for (let i = 0; i < k && start.next; i++) {
start = start.next;
}
}
return dummy.next;
}
// 测试用例
const head1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const k1 = 2;
const result1 = reverseLinkedList(head1, k1);
console.log(result1); // 输出：2->1->4->5->3
const head2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const k2 = 3;
const result2 = reverseLinkedList(head2, k2);
console.log(result2); // 输出：3->2->1->4->5
const head3 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const k3 = 6;
const result3 = reverseLinkedList(head3, k3);
console.log(result3); // 输出：1->2->3->4->5
</script>