如何在javascript中递归地反转一个链表
How to reverse a linkedlist recursively in javascript?
我试图在Javascript
中递归地逆转linkedlist
。我自己试过了,也在网上找过了。但没有成功。下面是我尝试的代码:
var Node = (function(){
function Node(val){
this.elem = val;
this.next = null;
}
return Node;
})();
var SLinkedlist = (function(){
function SLinkedlist(){
this.head = new Node("head");
}
return SLinkedlist;
})();
SLinkedlist.prototype.find = function(val){
var current = this.head;
while(current !== null && current.elem !== val){
current = current.next;
}
return current;
}
SLinkedlist.prototype.insert = function(newVal, val){
var current = this.find(val);
var newNode = new Node(newVal);
newNode.next = current.next;
current.next = newNode;
}
function reverseLinkedList(list, previous){
//We need to use the the current setting of
//list.next before we change it. We could save it in a temp variable,
//or, we could call reverseLinkedList recursively
console.log(list);
if(list !== null && list.next !==null){
reverseLinkedList(list.next, list);
}
console.log("after recursion!")
console.log(list);
//Everything after 'list' is now reversed, so we don't need list.next anymore.
//We passed previous in as an argument, so we can go ahead and set next to that.
list.next = previous;
}
reverseLinkedList(list.head, null);
有人能帮我吗?
假设您的列表与此类似:
var list =
{
name: "1",
next: {
name: "2",
next: {
name: "3",
next: {
name: "4"
}
}
}
};
console.log("Original list");
var head = list;
while (head != undefined) {
console.log(head.name);
head = head.next;
}
呈现
Original list
1
2
3
4
你可以用递归函数反转它,像这样:
head = reverse(list, undefined);
console.log("Reverse list");
while (head != undefined) {
console.log(head.name);
head = head.next;
}
function reverse(list, prev) {
// if this is the last node, switch it with previous and return
if (list.next == undefined) {
list.next = prev;
return list;
}
// otherwise, switch it with the reverse of what is next
var ret = reverse(list.next, list);
list.next = prev;
return ret;
}
呈现
Reverse list
4
3
2
1
它是如何工作的?它基于以下原则:
Reverse([1 2 3 4]) ==
[ Reverse([2 3 4]) 1 ] ==
[ Reverse([3 4]) 2 1 ] ==
[ 4 3 2 1 ]
这是我的面向对象递归解决方案。
function Node(value) {
this.value = value;
this.next = null;
}
function SLinkedList(node) {
if (node) {
this.head = node;
} else {
this.head = null;
}
}
SLinkedList.prototype.prepend = function(node) {
node.next = this.head;
this.head = node;
}
SLinkedList.prototype.print = function() {
var arr = [];
var current = this.head;
while (current !== null) {
arr.push(current.value);
current = current.next;
}
alert(arr.join(' '));
}
SLinkedList.prototype.reverse = function() {
if (this.head === null || this.head.next === null) {
return;
}
var first = this.head;
var rest = new SLinkedList(this.head.next);
rest.reverse();
first.next.next = first;
first.next = null;
this.head = rest.head;
}
var list = new SLinkedList();
list.prepend(new Node(4));
list.prepend(new Node(3));
list.prepend(new Node(2));
list.prepend(new Node(1));
list.print();
list.reverse();
list.print();
JSFiddle: http://jsfiddle.net/5c9gtstk/1/
关于你的代码的一些提示,不是100%错误,但我认为会有所帮助,主要是为了复习你的链表:
- 这是不典型的有一个"头"作为值的第一个节点,虽然你可以做到这一点-只是从你的"头"节点的
next
开始。 -
console.log(list)
行没有告诉太多关于发生了什么,因为数据结构只包含elem
和next
,这就是为什么我写了一个打印函数。这可以帮助你调试。 - 你的插入函数也是非典型的,但这不是一个真正的问题在这个算法:)
http://www.thatjsdude.com/interview/linkedList.html#singlyLinkedList有一个简单、简明的解释,告诉你如何做到这一点。
关于你的反向算法,你几乎有了正确的想法。我在这里给出的主要技巧是绘制出递归调用中发生的事情!慢慢地手动一步一步地执行代码。这需要几秒钟的时间,但会让一切都100%清楚。
具体来说,在反转列表的其余部分后,list.next = previous;
是所有您需要做的吗?还有一些其他的指针需要修改。
其他人,包括这里的一个答案,已经给出了比我更好的解释。同样,图表是关键。http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/有一个很好的、简短的解释——直接跳到递归方法的部分。
我上面的2个链接是1个浏览器页面。我建议你看一看
要反转链表,我们可以使用简单的递归方法。将链表的头传递给下面的方法。
reverse( head ) {
if( head ) {
reverse( head.next );
console.log( head.data );
}
}
完整的工作解决方案在这里
为了补充上述答案,下面是ES6/JavaScript中的后进先出(LIFO)链表实现,具有递归地反转列表和就地(不创建新列表)的函数:
class Element {
constructor(value) {
this.value = value;
this.next = null;
}
}
class List {
constructor(arr) {
this.head = null;
if (arr) {
arr.forEach(el => this.add(new Element(el)));
}
}
get length() {
return this.head ? this.countElements(1, this.head) : 0;
}
add(el) {
const element = el;
element.next = this.head;
this.head = element;
}
countElements(count, element) {
return element.next ? this.countElements(count + 1, element.next) : count;
}
toArray(arr = [], element = this.head) {
arr.push(element.value);
return element && element.next ? this.toArray(arr, element.next) : arr;
}
reverse(prev = null) {
if (this.head.next) {
const current = this.head;
this.head = this.head.next;
current.next = prev;
return this.reverse(current);
}
this.head.next = prev;
return this;
}
}
const list = new List([1, 2, 3, 4, 5, 6, 7 , 8 ,9 , 10]);
console.log(list.toArray().toString()); // returns LIFO list as array (last list el = first array el)
console.log(list.reverse().toArray().toString()); // returns LIFO list reversed as array(first first)
这两个现有的答案为这个问题提供了很好的解决方案,但是我认为了解代码为什么不能工作可能会有所帮助。在javascript中,当执行递归调用时,将创建一个具有自己作用域的新闭包。所以在最后一个调用中,也就是"tail"所在的地方,引用它的list
变量实际上是一个局部变量,它覆盖了环境中现有的list
。因此,当函数退出时,如果不返回这个本地list
,对它的引用将丢失。
其他两个答案所做的是返回该值并将其存储在临时变量中(代码中的注释实际上没有帮助…你需要把尾巴存储在某个地方,否则你会丢失它!)
您可能知道,如果所有这些都在您的反向函数中处理,则不会污染全局作用域。
另外@bbill是绝对正确的手动执行代码,一步一步地在像Chrome devtools这样的东西。这真的可以很好地了解正在发生的事情。
你可以试试这个方法:我从这里参考:https://www.youtube.com/watch?v=KYH83T4q6Vs基本上,一旦递归到达最后一个节点,我们就会将指针从最后一个节点更改为指向前一个节点。
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
reverseLLRec(node) {
if (!node.next) {
this.head = node;
return;
}
this.reverseLLRec(node.next);
const curr = node.next;
curr.next = node;
node.next = null;
}
}
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
reverseLLRec(node) {
if (!node.next) {
this.head = node;
return;
}
this.reverseLLRec(node.next);
const curr = node.next;
curr.next = node;
node.next = null;
}
insertAtLast(data) {
const node = new Node(data);
if (this.head === null) {
this.head = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
}
printList() {
let curr = this.head;
let list = [];
while (curr) {
list.push(curr.val);
curr = curr.next;
}
console.log(list);
}
}
const ll = new LinkedList();
ll.insertAtLast(1);
ll.insertAtLast(2);
ll.insertAtLast(3);
ll.insertAtLast(4);
ll.insertAtLast(5);
console.log('Before reverse:');
ll.printList();
ll.reverseLLRec(ll.head);
console.log('After reverse:');
ll.printList();
- 多个mp3下载链接到一个zip文件,用于下载javascript或jquery
- 删除时出现Javascript链表问题
- 多个下载链接到一个zip文件,然后再下载javascript
- shadowbox内容链接到一个新的shadowbox
- Javascript一页滚动脚本滚动到每个点击的链接一个接一个
- 如何访问AngularJS promise链中上一个promise的结果
- 使用jQuery链接到一个页面,然后跳转到一个特定的标题
- JS中的专用链表
- 如何将 hasNext() 和 hasPrevious() 方法用于 Node 的“智能列表”链表模块
- 我想将这段javascript链接到一个按钮
- 当我将一个对象链接到一个对象数组时,两个对象的值是如何链接的
- JavaScript:用于查找链表节点的递归函数返回错误的节点
- 有没有办法将两个HTML ID链接到一个javascript函数
- JavaScript 如何处理传递给与这个链表示例相关的函数的对象
- 如何破解LiveScript以便在html中链接一个单独的文件
- 不是jQuery链中下一个元素上的这个选择器
- 如何在javascript中实现函数调用的任意链表
- Javascript:检测并从循环链表中删除一个循环
- 如何链接一个表单输出到一个谷歌融合表查询使用javascript
- 如何在javascript中递归地反转一个链表