TypeScript算法专题 -
[单链表2] 单链表节点的索引、结点删除与链表反转
运行TypeScript方法的补充
在开始本本章的任务前先要补充一个技术，那就是在命令行中直接运行TypeScript代码。上一节中，我们使用的是将TypeScript编译成JavaScript后，在Html中引入该JavaScript文件后运行。然而这种方法很不直接也很麻烦，更加不符合我们有如Java、Python等等其它后端编程语言的开发者的习惯。为了像在命令行窗口中运行Java和Python那样运行TypeScript 脚本，我们需要在全局安装了typeScrippt包的基础上安装ts-node：
npm install ts-node --g
安装完成后，我们在一个目录下建立一个新的.ts文件tsnode.ts并添加以下代码：
// tsnode.ts console.log("Hello ts-node!");
通过cd命令进入到该文件所在目录，使用ts-node像执行Java脚本那样执行该.ts文件中的代码，即如下运行命令：
ts-node tsnode.ts
可以看到在控制台（命令行）显示内容Hello ts-node!，如图所示：
【注意】
TypeScript中没有指针的概念，因此在专题前两篇文章中我们用的是一种比较麻烦的方法去模拟，实际上是建立一个新的结点链来实现功能。
第三篇 《链表实现中的一些问题总结与改进》将讲解在JavaScript和TypeScript中的变量引用，并对我们的链表中的相应内容进行简化。
1. 节点替换
节点替换即将链表中的某一个节点替换成一个新的节点。
其步骤如下：
- 确定待替换节点位置；
- 用新节点接收待替换节点的后继指针
next； - 将新节点挂载到待替换节点的前驱。
replace(index:number, nodes:Lnode){ /** * 将索引为`index`处的结点替换为新结点`nodes` * 其中`node`既可以是单个节点又可以是后继指针非空的一系列节点 * @param index {number} 将要被替换掉的节点的索引 * @param nodes {Lnode} 替换上去的新节点 */ function count_len_nodes(node:Lnode):number{ /** 用于当传入为止个数的节点链而非单个节点时，计算传入新传入的节点链长度 */ let ct:number = 0; let pt:Lnode = node; while(pt!= null){ ct++; pt = pt.next; } return ct; } if(nodes==null){throw "ValueError: Replacing with null is prohibited." }else{ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else{ let len_nodes:number = 0; if(nodes.next == null){ // 传入单个节点 len_nodes = 1 }else{ // 传入的节点为有后继的节点链 len_nodes = count_len_nodes(nodes); }; let pointer: Lnode = this.head; let result:Lnode = new Lnode(); for(let i=0; i<index; i++){ result.merge(new Lnode(pointer.data)); pointer = pointer.next; } nodes.merge(pointer.next) // nodes先接纳原先索引为`index`处节点的后继 result.merge(nodes) // 将原本接索引为`index`处的位置替为新节点。 this.head = result; this.length = this.length - 1 +len_nodes // 更新链表长度 } } }
2. 弹出链表首尾的节点
2.1 弹出链表首部节点
以下我们认定链表头部第一个节点的位置为该链表的最左边。从左边弹出一个节点需要完成以下几个步骤：
- 获取链表的头节点；
- 将头指针指向原头节点的后继节点指针；
- 返回获取的原头节点。
pop_left():Lnode{ /** * 弹出最左边的一个结点并返回 * @returns node {Lnode} 原链表最左侧的一个结点 */ if(this.head==null){throw "PopEmptyError: Unable to pop up node from an empty linked list.";} else{ let node = this.head; this.head = this.head.next; // 头结点右移一个 node.next = null; // 斩断后继联系 this.length = this.length - 1; // 更新链表长度 if(this.length==0){this.head=null}; return node; } }
代码测试：
let list = new LinkList([0,1,2]); // 建立链表，它原有3个结点，结点的数据域分别为数字1、2、3 console.log(list.pop_left()); // 弹出第1个结点 console.log(list.length); // 输出长度 console.log(list.pop_left()); // 弹出第2个结点 console.log(list.length); console.log(list.pop_left()); // 弹出第3个结点 console.log(list.length);
Out[]:
Lnode { empty: false, data: 0, next: null } 2 Lnode { empty: false, data: 1, next: null } 1 Lnode { empty: false, data: 2, next: null } 0
如果当链表已经空了却还在进行pop_left()，则将看到错误提示，如图所示：
2.2 弹出链表尾部节点
从又边弹出一个节点需要完成以下几个步骤：
- 逐渐指向链表尾部最后一个节点的前一个节点；
- 从该节点的后继节点指针
next获取链表尾部节点； - 斩断该节点与链表尾部节点的练习（清空其
next）； - 返回所获取的链表尾部节点。
pop():Lnode{ /** * 弹出最右边的一个结点并返回 * @returns node {Lnode} 原链表最右侧的一个结点 */ if(this.head==null){throw "PopEmptyListError: Unable to pop up node from an empty linked list.";} else{ let pointer = this.head; let result:Lnode = new Lnode(); while(pointer.next!=null){ result.merge(new Lnode(pointer.data)); pointer = pointer.next; }; this.head = result; this.length = this.length - 1; if(this.length==0){this.head=null}; return pointer; } }
测试代码：
let list = new LinkList([0,1,2]); // 建立链表，它原有3个结点，结点的数据域分别为数字1、2、3 console.log(list.pop()); // 弹出第1个结点 console.log(list.length); // 输出长度 console.log(list.pop()); // 弹出第2个结点 console.log(list.length); console.log(list.pop()); // 弹出第3个结点 console.log(list.length);
Out[]:
Lnode { empty: false, data: 2, next: null } 2 Lnode { empty: false, data: 1, next: null } 1 Lnode { empty: false, data: 0, next: null } 0
如果当链表已经空了却还在进行pop()，则将看到错误提示，如图所示：
3. 节点删除
3.1 删除指定索引index处的节点
其步骤如下：
- 从原头节点逐渐指向索引结点的前一个结点；
- 将这个结点的后继指针
next由指向索引结点改为指向索引结点的next所指结点
del(index:number){ /** * 删除索引号为`index`的某个结点，保留其后继结点 * @param index {number} 将被删除的结点的索引号 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(this.head==null){throw "EelEmptyListError: Unable to pop up node from an empty linked list.";} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!";} else{ if(index==0){ this.pop_left(); }else{ let pointer:Lnode = this.head; let result:Lnode = new Lnode(); for(let i=0; i<index; i++){ result.merge(new Lnode(pointer.data)); pointer = pointer.next; // 指向下一个 } result.merge(pointer.next); this.head = result; } } }
代码测试
【T-1】
let list = new LinkList([0,1,2]); list.del(2); console.log(list.toArray())
Out[]:
[ Lnode { empty: false, data: 0, next: null }, Lnode { empty: false, data: 1, next: null } ]
【T-2】
let list = new LinkList([0,1,2]); list.del(1); console.log(list.toArray())
Out[]:
[ Lnode { empty: false, data: 0, next: null }, Lnode { empty: false, data: 2, next: null } ]
【T-3】
let list = new LinkList([0,1,2]); list.del(0); console.log(list.toArray())
Out[]:
[ Lnode { empty: false, data: 1, next: null }, Lnode { empty: false, data: 2, next: null } ]
3.2 删除索引index处及其后继结点
3.3 删除两个索引值a（包含）、b（包含）的所有结点
3.2和3.3两个小节采用重载的方式同时实现，代码如下：
drop(index: number); drop(index:[number,number]); drop(index){ if(this.head==null){throw "EelEmptyListError: Unable to pop up node from an empty linked list.";} else{ if(typeof(index)=="number"){ /** * 删除索引号为`index`的某个结点及其之后的所有结点 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!";} else{ let pointer:Lnode = this.head; let result:Lnode = new Lnode(); for(let i=0; i<index; i++){ result.merge(new Lnode(pointer.data)); // 记录先前的 pointer = pointer.next; // 指向下一个 }; this.head = result; } }else if(typeof(index)=="object"){ /** * 删除索引号从`a`（包含）到`b`（包含）的一段结点 */ let a:number = index[0]; let b:number = index[1]; if(a>b){ a = index[1]; b = index[0]; } if(a<0){throw "ValueError: Index must be a positive integer!"} else if(b+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else{ let pointer:Lnode = this.head; let result:Lnode = new Lnode(); let len: number = 0; // 长度计数器 // [0:a-1] while(a>0){ result.merge(new Lnode(pointer.data)); // 收纳索引a前的结点 len++; // 长度计数器自增 pointer = pointer.next; // 游标后指 a--; }; // [a:b] while(len<b+1){ // 跳过[a,b] pointer = pointer.next; // 游标后指 len++; } // [b+1:] while(pointer!=null){ result.merge(new Lnode(pointer.data)); pointer = pointer.next; } this.head = result; } } else{ throw "TypeMismatchError: Type of actual parameter not match any overloaded method!" } } }
4. 链表反转
4.1 在不改变原有结点的条件下返回反转后新链表
由于我们之前已经实现了链表转数组的方法，即LinkList.toArray()方法，因此这里我们采用一种及其简单的方式来获取反转后的新链表，即利用TypeScript中数组的反转方法。具体请看代码：
getReverse():LinkList{ /** * 返回原链表反转后的新链表 * 该方法不会改变原链表 */ let result: LinkList = new LinkList(); let nodes: Lnode[] = []; nodes = this.toArray().reverse(); for(let i=0; i<nodes.length; i++){ result.append(nodes[i]) } return result }
代码测试：
let list1 = new LinkList(["我","爱","你"]) // 原链表 console.log(list1.toArray()) // 原链表转数组输出 let list2: LinkList = list1.getReverse() // 获取原链表反转后的新链表 console.log(list2.toArray()) // 新链表转数组输出
Out[]:
[ Lnode { empty: false, data: '我', next: null }, Lnode { empty: false, data: '爱', next: null }, Lnode { empty: false, data: '你', next: null } ] [ Lnode { empty: false, data: '你', next: null }, Lnode { empty: false, data: '爱', next: null }, Lnode { empty: false, data: '我', next: null } ]
可以看到，我们获取的结点数组中的元素顺序与原数组恰好是相反的，这意味着相应的新链表实现了原连标配的反转。
4.2 直接反转原链表所有结点
与4.1节获取反转后的新链表的getReverse()方法不同，本节的的reverse()方法采用直接反转原链表。这里改变的是原链表中元素的顺序，而并不会返回一个新的链表，请看代码：
reverse():void{ /** * 将原链表反转，不反返回何结果 * 该方法将会改变原链表 */ if(this.head == null){ this.head = null; }else{ let result:Lnode = new Lnode(); while(this.head.next!=null){ let node = this.pop_left(); // 新结点为新倒出来的头 if(!result.empty){ // 第一次无先前链头，跳过之 node.next = result; // 新结点后继为之前的头链 } result = node; // 新头链成为旧头链 } // 挂载最后一个头 this.head = this.pop_left(); this.head.next = result; } }
附：目前的完整代码
import {range} from "./tools"; class Lnode{ /** * 链表结点类，结点是构成链表的基础单元。 * @class Lnode * @constructor * @param next {Lnode} 指向下一结点的指针 * @param data {string | number} 结点的数据。这里只放一些字符串数据或者数字。 */ next: Lnode | undefined | null; // 结点类型（Lnode）的nest也是结点类型Lnode，undefined和null是任意类型的子类型也可以不写 data: any; empty: boolean; // 描述结点是否为空，这个是配合初始化一个空结点使用的 constructor(data?:string | number){ if(data!=undefined){ // 非空结点 this.empty = false; // 空标识置为假 this.data = data; this.next = null; }else{ // 空结点，即值构建结点对象但实际上不存在结点 this.empty = true; // 空标识置为真 this.data = null; this.next = null; } } merge(node: Lnode){ /** * 将另一个结点（链）合并到本结点（或链）的尾部 * @param node {Lnode} 需要插入链表尾部的新结点 */ if(this.empty==true){ // 空结点 this.empty =false; this.data = node.data; }else{ if(this.next == null){ // 没有链接下一个 this.next = node; }else{ // 有链接下一个 this.next.merge(node); } } } } class LinkList{ /** * 单链表类 * @class LinkList * @constructor * @param head {Lnode} 链表的头指针，其`next`用于挂载结点 * @param length {number} 链表的长度 */ head: Lnode | undefined| null; length: number; // 链表所容纳结点的个数 constructor(datas?:any[]){ /**初始化 */ if(datas==undefined){ this.head = null; // 初始化为null算作空链表，不计算长度 this.length = 0; }else{ for(let i=0; i<datas.length; i++){ this.append(new Lnode(datas[i])) } this.length = datas.length; // 指定一组数据初始化则初始后长度为这组数据元素的个数 } } is_empty(){ /** * 判断链表是否为空 * 只需要判断头结点是否为空，若头结点为空则为空链表，否则不是。 * @return {Boolean} true:链表为空; false:链表非空。 */ if(this.head == null){ return true; }else{ return false; } } top():Lnode{ /** * 获取链表头结点 */ let node = this.head; node.next = null; return node; } clear(){ /** * 清空链表，只要把头结点干废，整个链表直接就完蛋（清空）了 */ this.head = null; this.length = 0; } append(node: Lnode){ /** * 将新结点挂载到链表尾部 * @param node {Lnode} 需要插入链表尾部的新结点 */ if(this.head == null){ this.head = node; this.length = this.length + 1; }else{ this.head.merge(node); this.length = this.length + 1; } } append_left(node: Lnode){ /** * 将一个新结点插入到链表首部 * @param node {Lnode} 要从左侧也就是链头插入的新结点 */ if(this.head == null){ this.head = node; // 若为空链表，直接将链表头设置为该结点 this.length = this.length + 1; // 增加结点长度 }else{ // 先将新结点的`next`指向原第一个结点 node.next = this.head; // 再将`head`指向新的结点 this.head = node; this.length = this.length + 1; // 增加结点长度 } } get(index: number):Lnode{ /** * 获取索引号为`index`的结点。 * 索引号是从数字`0`开始计算的 * @param index {number} 索引号 * @return node {Lnode} 索引得到地节点 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else{ let pointer:Lnode = this.head; // 从头结点开始 range([index]).forEach(() => { pointer = pointer.next; // 逐个指向下一个结点 }); pointer.next = null; // 斩断后继 return pointer; } } get_data(index: number){ /** * 索引节点地数据 * @param index {number} 索引号 * @return data {any} 链表中与索引号对应地节点地数据域内容 */ return this.get(index).data } insert(index:number, node:Lnode){ /** * 在链表的第`index`个节的位置挂载新的结点`node`，其中从结点为`index = 0`开始编号 * 也就是说，新的结点索引号将为`index`，而这个结点将挂载到索引号为`index-1`的结点后面 * * @param index {number} 新结点插入的索引号 */ if(node!=null && node.next==null){node.next = null;}; // 只允许插入单个结点，若有后继直接切断 if(index==0){ node.next = this.head; // 先收小弟 this.head = node; // 再上位 }else{ let pointer: Lnode = this.head; // 从头结点开始 let results: Lnode = new Lnode(); // 空结点 for(let i=0; i<index; i++){ results.merge(new Lnode(pointer.data)); // 逐个记录先驱结点 pointer = pointer.next; // 逐个指向下一个结点 } node.next = pointer; // 先收小弟 results.merge(node); // 再上位 this.length = this.length + 1; // 更新结点长度 this.head = results; } } toArray():Lnode[]{ /** * 获取链表结点依次构成的数组 * @returns elem {Lnode[]} 以此装载了被遍历到的所有结点（这里其中每个结点都是孤立、干掉next的） */ let elm: Lnode[] = []; // 准备好用于容纳所有的结点 let pointer:Lnode = this.head; // 挂载操作一开始时指针指向头部结点、 if(pointer==null){ // 空链表，不仅要返回一个空数组，还要抛出提示 console.warn("Warning: It seems that you hava traversed an empty Linked List!"); return elm; }else{ // 非空链表 while(pointer.next != null){ // 存在下一个结点时 if(pointer == null){ // 停止（拦截）条件：（直到）结点为`null` break; }else{ // 获取当前结点剔除链接关系的`孤立结点`挂载结点数组 elm.push(new Lnode(pointer.data)); } pointer = pointer.next; // 指向后继 } elm.push(new Lnode(pointer.data)); // 最后一个元素 return elm; } } replace(index:number, nodes:Lnode){ /** * 将索引为`index`处的结点替换为新结点`nodes` * 其中`node`既可以是单个节点又可以是后继指针非空的一系列节点 * @param index {number} 将要被替换掉的节点的索引 * @param nodes {Lnode} 替换上去的新节点 */ function count_len_nodes(node:Lnode):number{ /** * 用于当传入为止个数的节点链而非单个节点时， * 计算传入新传入的节点链长度 */ let ct:number = 0; let pt:Lnode = node; while(pt!= null){ ct++; pt = pt.next; } return ct; } if(nodes==null){throw "ValueError: Replacing with null is prohibited." // 如果允许替换为`null`将把后续节点全部干掉， // 这就相当于执行删除的功能。因此禁止替换为null。 }else{ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else{ let len_nodes:number = 0; if(nodes.next == null){ // 传入单个节点 len_nodes = 1 }else{ // 传入的节点为有后继的节点链 len_nodes = count_len_nodes(nodes); }; let pointer: Lnode = this.head; let result:Lnode = new Lnode(); for(let i=0; i<index; i++){ result.merge(new Lnode(pointer.data)); pointer = pointer.next; } console.log("nodes=",nodes) nodes.merge(pointer.next) // nodes先接纳原先索引为`index`处节点的后继 result.merge(nodes) // 将原本接索引为`index`处的位置替为新节点。 this.head = result; this.length = this.length - 1 +len_nodes // 更新链表长度 } } } drop(index: number); drop(index:[number,number]); drop(index){ if(this.head==null){throw "EelEmptyListError: Unable to pop up node from an empty linked list.";} else{ if(typeof(index)=="number"){ /** * 删除索引号为`index`的某个结点及其之后的所有结点 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!";} else{ let pointer:Lnode = this.head; let result:Lnode = new Lnode(); for(let i=0; i<index; i++){ result.merge(new Lnode(pointer.data)); // 记录先前的 pointer = pointer.next; // 指向下一个 }; this.head = result; } }else if(typeof(index)=="object"){ /** * 删除索引号从`a`（包含）到`b`（包含）的一段结点 */ let a:number = index[0]; let b:number = index[1]; if(a>b){ a = index[1]; b = index[0]; } if(a<0){throw "ValueError: Index must be a positive integer!"} else if(b+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else{ let pointer:Lnode = this.head; let result:Lnode = new Lnode(); let len: number = 0; // 长度计数器 // [0:a-1] while(a>0){ result.merge(new Lnode(pointer.data)); // 收纳索引a前的结点 len++; // 长度计数器自增 pointer = pointer.next; // 游标后指 a--; }; // [a:b] while(len<b+1){ // 跳过[a,b] pointer = pointer.next; // 游标后指 len++; } // [b+1:] while(pointer!=null){ result.merge(new Lnode(pointer.data)); pointer = pointer.next; } this.head = result; } } else{ throw "TypeMismatchError: Type of actual parameter not match any overloaded method!" } } } del(index:number){ /** * 删除索引号为`index`的某个结点，保留其后继结点 * @param index {number} 将被删除的结点的索引号 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(this.head==null){throw "EelEmptyListError: Unable to pop up node from an empty linked list.";} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!";} else{ if(index==0){ this.pop_left(); }else{ let pointer:Lnode = this.head; let result:Lnode = new Lnode(); for(let i=0; i<index; i++){ result.merge(new Lnode(pointer.data)); // 记录先前的 pointer = pointer.next; // 指向下一个 } result.merge(pointer.next); this.head = result; } } } pop():Lnode{ /** * 弹出最右边的一个结点并返回 * @returns node {Lnode} 原链表最右侧的一个结点 */ if(this.head==null){throw "PopEmptyListError: Unable to pop up node from an empty linked list.";} else{ let pointer = this.head; let result:Lnode = new Lnode(); while(pointer.next!=null){ result.merge(new Lnode(pointer.data)); pointer = pointer.next; }; this.head = result; this.length = this.length - 1; if(this.length==0){this.head=null}; return pointer; } } pop_left():Lnode{ /** * 弹出最左边的一个结点并返回 * @returns node {Lnode} 原链表最左侧的一个结点 */ if(this.head==null){throw "PopEmptyError: Unable to pop up node from an empty linked list.";} else{ let node = this.head; this.head = this.head.next; // 头结点右移一个 node.next = null; // 斩断后继联系 this.length = this.length - 1; // 更新链表长度 if(this.length==0){this.head=null}; return node; } } reverse():void{ /** * 将原链表反转，不反返回何结果 * 该方法将会改变原链表 */ if(this.head == null){ this.head = null; }else{ let result:Lnode = new Lnode(); while(this.head.next!=null){ let node = this.pop_left(); // 新结点为新倒出来的头 if(!result.empty){ // 第一次无先前链头，跳过之 node.next = result; // 新结点后继为之前的头链 } result = node; // 新头链成为旧头链 } // 挂载最后一个头 this.head = this.pop_left(); this.head.next = result; } } getReverse():LinkList{ /** * 返回原链表反转后的新链表 * 该方法不会改变原链表 */ let result: LinkList = new LinkList(); let nodes: Lnode[] = []; nodes = this.toArray().reverse(); for(let i=0; i<nodes.length; i++){ result.append(nodes[i]) } return result } }
其中get()方法用到的import从tools.ts导入了range函数，这部分内容如下：
export function range(x:[number]):number[]; // [end] export function range(x:[number,number]):number[]; // [start, end] export function range(x:[number,number,number]):number[]; // [start, end, step] export function range(x){ let ar:number[] = []; if(x.length==1){ /**重载：传入数组只有1个元素 */ for(let i=0; i<x[0]; i++){ ar.push(i) } }else if(x.length == 2){ /**重载：传入2元素数组 */ for(let i=x[0]; i<x[1]; i++){ ar.push(i); } }else if(x.length==3){ /**重载：传入3元素数组 */ for(let i=x[0]; i<x[1]; i+=x[2]){ ar.push(i); } } return ar; }
如果不想这样也可以将get()方法该为：
get(index: number){ /** * 获取索引号为`index`的结点。 * 索引号是从数字`0`开始计算的 * @param index {number} 索引号 * @return node {Lnode} 索引得到地节点 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else{ let pointer:Lnode = this.head; // 从头结点开始 for(let i=0; i<index;i++){ pointer = pointer.next; // 逐个指向下一个结点 } pointer.next = null; // 斩断后继 return pointer; } }
这样，导入语句即：
import {range} from "./tools";
可以相应地删除掉。
