首页 > 代码库 > 面试题5：JS实现从尾到头打印单链表
面试题5：JS实现从尾到头打印单链表
单链表，在内存中所占地址是不连续的。所以遍历单链表时：需要从头遍历。而题目要求输出的顺序：从尾到头。也就是说第一个遍历到的节点最后一个输出，而最后一个遍历到的节点第一个输出。这就是典型的“后进先出”，我们可以用栈来实现这种顺序。
例题一共包含四个文件。运行程序前提：项目安装了nodejs
1.stack_list.js:实现了一个普通的栈。
/** * Created by ym-Wang on 2016/8/16. */function Stack(){ this.top = null; this.size = 0;}Stack.prototype = { initStack:function(){ return new Stack(); }, push:function(data){ var node = { data:data, next:null }; node.next = this.top; this.top = node; this.size++; }, pop:function(){ if(this.isStackEmpty()){ console.log("stack is Empty"); return false; } var out = this.top; this.top = this.top.next; if(this.size > 0){ this.size--; } return out.data; }, clearStack:function(){ this.top = null; this.size = 0; }, isStackEmpty:function(){ return this.top == null?true:false; }};function stackConstructor(){ return new Stack();};exports.stackConstructor = stackConstructor;2.createNode.js:用于初始化节点
(function(){ "use strict"; function Node(element){ this.element = element; this.next = null; } function nodeConstructor(element){ return new Node(element); }; exports.nodeConstructor = nodeConstructor;})();3.createList.js:实现一个单链表
(function(){ "use strict"; var node = require("./createNode.js"); function LinkedList(){ this._head = node.nodeConstructor("This is Head Node"); this._size = 0; } LinkedList.prototype = { isEmpty:function(){ if(this._size == 0){ return true; }else{ return false; } }, size:function(){ return this._size; }, getHead:function(){ return this._head; }, display:function(){ var currNode = this.getHead().next; while(currNode){ console.log(currNode.element); currNode = currNode.next; } }, remove:function(item){ if(item){ var preNode = this.findPre(item); if(preNode == null){ return; } if(preNode.next != null){ preNode.next = preNode.next.next; this._size--; } } }, add:function(item){ this.insert(item); }, insert:function(newElement,item){ //在指定位置item后插入newElement节点，如果未找到item，则插入到链表结尾。 var newNode = node.nodeConstructor(newElement); var finder = item?this.find(item):null; if(!finder){ var last = this.findLast(); last.next = newNode; }else{ newNode.next = finder.next; finder.next = newNode; } this._size++; }, findLast:function(){ //返回最后一个及节点 var currNode = this.getHead(); while(currNode.next){ currNode = currNode.next; } return currNode; }, findPre:function(item){ //返回指定元素的上一个节点 var currNode = this.getHead(); while(currNode.next != null&&currNode.next.element !=item){ currNode = currNode.next; } return currNode; }, find:function(item){ if(item == null){ return null; } var currNode = this.getHead(); while(currNode && currNode.element != item){ currNode = currNode.next; } return currNode; } }; exports.linkedList= new LinkedList();})();4.desending.js：倒序输出单链表
(function(){ var singleList = require("./createList.js"); var stack_list = require("./stack_list.js"); var list = singleList.linkedList; var stack = stack_list.stackConstructor(); list.add(1); list.add(12); list.add(123); list.add(1234); var curNode = list.getHead(); while(curNode.next !== null){ stack.push(curNode.next.element); curNode = curNode.next; } while(stack.size!=0){ var ele = stack.pop(); console.log(ele); }})();注意:我的项目中这四个文件是在同一目录下的。如果不在同一目录下，需要修改require的路径参数。
面试题5：JS实现从尾到头打印单链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。