// 创建一个链表 /** * 创建一个链表的节点,每一个链表都是跟节点 * @param value * @constructor */ function Node(value) { this.value = value; this.next = null; } let a = new Node('a'); let b = new Node('b'); let c = new Node('c'); let d = new Node('d'); let w = new Node('w'); a.next = b; b.next = c; c.next = d; /** * 获取链表的长度,原型方法 * @returns {number} */ Node.prototype.length = function () { let temp = this, index = 0; while (temp) { index++; temp = temp.next; } return index; } /** * 获取链表的长度,直接方法 * @param root * @returns {number|*} */ function length(root) { if (!root) return 0; return 1 + getLength(root.next); } /** * 变量链表原型方法 */ Node.prototype.print = function () { function _print(root) { if (!root) return; console.log(root.value); _print(root.next); } _print(this); } /** * 打印链表的方法 * @param root * @returns {null} */ function print(root) { if (!root) return null; let temp = root; while (temp) { console.log(temp.value); temp = temp.next; } } /** * 通过下标获取链表的值, 原型方法 * @param i * @returns {null} */ Node.prototype.getValue = function (i) { if (!this || i < 0 || i >= this.length()) return null; function _getValue(root, index) { if (!root) return null; else if (index === i) return root.value; else return _getValue(root.next, index + 1); } return _getValue(this, 0); } /** * 通过下标给链表设置值 * @param i * @param val */ Node.prototype.setValue = function (i, val) { if (!this || i < 0 || i > this.length()) return; function _setValue(root, index) { if (!root) return else if (index === i) root.value = val; else _setValue(root.next, index + 1); } _setValue(this, 0) } /** * 判断链表是否存在某个节点 * @param node {Node} 节点 * @returns {boolean} */ Node.prototype.has = function (node) { if (!this) return false; let temp = this; while (temp) { if (node instanceof Node && node.value === temp.value) return true; else temp = temp.next; } return false } /** * 判断节点是否存在链表中 * @param root{Node} * @param node{Node} * @returns {boolean} */ function has(root, node) { if (!root) return false; if (node instanceof Node && node.value === root.value) return true; else return has(root.next, node); } /** * 在一个节点之后加入一个新的节点 * @param node {Node} * @param val {String | Number} * @returns {boolean} */ Node.prototype.insertAfterNode = function (node, val) { if (!this || !this.has(node)) return; let temp = this; while (temp) { if (node instanceof Node && temp === node) { let newNode = new Node(val); newNode.next = temp.next; temp.next = newNode; return true; } temp = temp.next; } } /** * 在链表的任意一个节点后面插入一个新的节点 * @param root {Node} 链表 * @param node {Node} 节点 * @param val {String | Number} */ function insertAfterNode(root, node, val) { if (!root || !has(root, node)) return; if (node instanceof Node && root === node) { let newNode = new Node(val); newNode.next = root.next; root.next = newNode; } else { insertAfterNode(root.next, node, val); } } /** * 链表最后加入一个新的节点 * @param val {Number | String} * @returns {boolean|void} */ Node.prototype.push = function (val) { if (!this) return false; let temp = this; while (temp) { if (!temp.next) { temp.next = new Node(val); return this.print(); } temp = temp.next; } } /** * 在链表的最后加入新的节点 * @param root {Node} * @param val {String | Number} * @returns {boolean} */ function push(root, val) { if (!root) return false; if (!root.next) { root.next = new Node(val); } else push(root.next, val); } /** * 通过节点删除一个节点 * @param node {Node} * @returns {boolean|void} */ Node.prototype.del = function (node) { if (!this || !this.has(node) || node === this) return false; let temp = this; while (temp) { if (temp.next === node && node instanceof Node) { let nextNode = temp.next; temp.next = temp.next.next; nextNode.next = null; return this.print(); } else temp = temp.next; } } /** * 删除一个节点 * @param root {Node} * @param node {Node} * @returns {boolean} */ function del(root, node) { if (!root || !has(root, node) || (root === node && node instanceof Node)) return false; else if (root.next === node) { let rootNextNode = root.next; root.next = root.next.next; rootNextNode.next = null; } else del(root.next, node); } /** * 字符串的逆置 */ Node.prototype.reverse = function () { if (!this) return; function _reverse(root) { if (!root) return; if (!root.next.next) { let node = root.next; root.next.next = root; root.next = null; return node; } else { let res = _reverse(root.next); root.next.next = root; root.next = null; return res; } } return _reverse(this).print(); }