今日问题:如何实现反转链表?
Q:如果在前端面试中,被问到如何实现反转链表,如果回答比较好,给出必要的代码示例
A:当被问到如何实现反转链表时,你可以首先解释反转链表的基本原理和步骤,然后给出相应的代码示例。下面是一个简单的 JavaScript 示例:
jsclass ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
function reverseLinkedList(head) {
let prev = null;
let current = head;
while (current !== null) {
const nextTemp = current.next; // 保存下一个节点的引用
current.next = prev; // 当前节点的 next 指向前一个节点
prev = current; // 更新 prev
current = nextTemp; // 更新 current
}
return prev; // 返回新的头节点
}
// 创建一个链表:1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
console.log("原始链表:");
let current = head;
while (current !== null) {
console.log(current.val);
current = current.next;
}
const newHead = reverseLinkedList(head);
console.log("反转后的链表:");
let newCurrent = newHead;
while (newCurrent !== null) {
console.log(newCurrent.val);
newCurrent = newCurrent.next;
}
在这个示例中,我们首先定义了一个 ListNode
类来表示链表的节点。然后,我们定义了一个 reverseLinkedList
函数来实现反转链表的功能。
在函数中,我们使用了三个指针 prev
、current
和 nextTemp
,分别表示前一个节点、当前节点和下一个节点。我们遍历链表,依次将当前节点的 next
指针指向前一个节点,然后更新 prev
、current
和 nextTemp
,直到遍历完整个链表。最后,我们返回新的头节点,完成链表的反转操作。
在示例中,我们创建了一个简单的链表,并打印出原始链表和反转后的链表,以验证我们的反转链表函数的正确性。
本文作者:CreatorRay
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!