js反转链表

js反转链表

在计算机科学中，链表是一种常见的数据结构，用于存储一系列的元素。链表中的每个元素被称为节点，每个节点包含一个值和指向下一个节点的指针。链表有很多种形式，其中最基本的形式是单向链表，每个节点只有一个指针指向下一个节点。在本文中，我们将讨论如何使用JavaScript来反转链表。

什么是反转链表？

反转链表是指将链表中的节点顺序颠倒过来。例如，给定一个链表1->2->3->4->5，反转后的结果为5->4->3->2->1。

方法一：迭代法

迭代法是一种比较直观的解决方法，其基本思路是从头到尾遍历链表，将每个节点的指针指向前一个节点。

下面是使用迭代法反转链表的JavaScript代码：

function reverseLinkedList(head) {
    let prev = null;
    let current = head;

    while (current !== null) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

我们定义了一个reverseLinkedList函数，参数为链表的头节点head。同时定义了prev和current两个变量，分别表示前一个节点和当前节点。在while循环中，我们不断更新current节点的next指针，使其指向prev节点。最后返回反转后的链表的头节点prev。

下面是一个示例，展示了如何使用上述代码反转一个链表：

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);

console.log("Original Linked List:");
let current = head;
while (current !== null) {
    console.log(current.value);
    current = current.next;
}

let reversedHead = reverseLinkedList(head);

console.log("Reversed Linked List:");
current = reversedHead;
while (current !== null) {
    console.log(current.value);
    current = current.next;
}

运行上面的代码，将会输出如下结果：

Original Linked List:
1
2
3
4
5
Reversed Linked List:
5
4
3
2
1

方法二：递归法

递归法也是一种常见的解决方法，其基本思路是不断递归调用反转函数，直到链表的末尾，然后反转链表。

下面是使用递归法反转链表的JavaScript代码：

function reverseLinkedListRecursive(head) {
    if (head === null || head.next === null) {
        return head;
    }

    let reversedHead = reverseLinkedListRecursive(head.next);
    head.next.next = head;
    head.next = null;

    return reversedHead;
}

我们定义了一个reverseLinkedListRecursive函数，使用递归的方式反转链表。首先判断链表是否为空或只有一个节点，如果是的话直接返回当前节点。否则，递归调用函数，直到链表末尾，然后开始反转链表。最后返回反转后的链表的头节点。

下面是一个示例，展示了如何使用上述代码反转一个链表：

let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);

console.log("Original Linked List:");
let current = head;
while (current !== null) {
    console.log(current.value);
    current = current.next;
}

let reversedHead = reverseLinkedListRecursive(head);

console.log("Reversed Linked List:");
current = reversedHead;
while (current !== null) {
    console.log(current.value);
    current = current.next;
}

运行上面的代码，将会输出如下结果：

Original Linked List:
1
2
3
4
5
Reversed Linked List:
5
4
3
2
1

总结

在本文中，我们讨论了如何使用JavaScript反转一个链表。我们介绍了两种方法：迭代法和递归法。迭代法是一种比较直观的解决方法，通过遍历链表来反转节点。递归法则是通过不断递归调用函数来反转链表。无论使用哪种方法，都可以很容易地实现链表的反转操作。