TypeScript算法专题 - [单链表3]
链表的合并
以及对TypeScript链表实现中的一些问题总结与改进
1. 使用console.log()进行代码分析时的意外情况提示
对于有过其它编程语言的读者，不论是C语言中的printf()函数，还是Python语言中的print()函数，又或者是Java语言中的println()函数，不管是编译型语言还是脚本语言，他们的执行都很能反应串行执行的特点，也就是说，执行语句是从开始到结束逐条执行。
“变态”的JavaScript以及其超集TypeScript让我们体验了一把与常识不一样的的感觉——使用conole.log()对象输出到控制台时，输出的内容往往并不是在该条console.log()语句执行时输出对象的”快照“。
举个例子
在浏览器环境中使用以下脚本：
let a = {"hello":"world"} console.log(a); // 第一次使用console.log()打印`a` a.hello = "世界"; console.log(a); // 第二次使用console.log()打印`a`
打开浏览器的控制台，可以看到：
不可思议的事情发生了—— 我们明明在第一次打印变量a后才对a进行修改，而实际结果却是两次打印a的值相同！
初次见到这种情况的你可能会到处找代码中的各种错误，一顿猛如虎的操作过后却发现没有任何的收获。不要慌，这时得赶紧想到可能真的并不是你的错误。
事实上，这种情况一般经常出现在浏览器运行代码的环境中。其原因时，浏览器在运行这段代码时可能会认为需要把控制台I/O延迟到后台。在这种情况下，等到浏览器控制台输出对象内容时，后面的语句可能已经执行，因此才会看到这样的输出结果。并且我们并没有办法确定什么时候控制台I/O会延迟，甚至是否能够被观察到。
2. 使用对对象的引用
TypeScript（或JavaScript）没有像C语言中那样的指针类型，不过却可以对对象进行引用。
先看两段代码：
【code1】
let a = 1; let b = a; b = 2; console.log("a=",a,"b=",b)
Out[]:
a= 1 b= 2
【code2】
class Test{ num:number; constructor(){ this.num = 1 } } let obj1: Test = new Test(); let obj2 = obj1; obj2.num = 6; console.log("obj1=",obj1)
Out[]:
obj1= Test { num: 6 }
在【code1】中可以看到，对变量b的赋值操作并没有改变变量a，
而在【code2】中对obj2的更改却同时更改了obj1！！——这是为什么呢？
首先必须要指出的是，JavaScript（包括TypeScript）中，并非一切皆对象！这一点上与彻底的面向对象编程语言Java和Python等有所不同。
在【code1】中当我们给变量a赋值1后，由于数值就不是JavaScript对象，因此let b = a不会使得变量b建立到一个对象的引用。正是因为如此，b = 2只是使变量b中存储的内容为数值2，并没有改变变量a。
在【code2】中，我们定义了一个Test类。首先我们构造了一个实例，通过变量obj1引用到该实例。在赋值语句let obj2 = obj1;中，由于obj1是对对象的引用，因此传递到变量obj2的也是同一个引用，意味着变量obj2和变量obj2一样，其中包含了的是同一个变量的地址，这个地址就是构造新的Test类时的这个类实例的地址。这就是为什么我们执行obj2.num=6时，obj1.num也同样变成了6。
3.对链表代码的调整
现在我们使用变量引用的方法，将前两篇博客中的单链表代码调整得到如下代码：
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{ let pointer = this.head; // 指向头节点 while(pointer.next != null){ pointer = pointer.next } pointer.next = node } } 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; // 从头结点开始 for(let i=0; i<index;i++){ 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):void{ /** * 在链表的第`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 = this.head; // 从头结点开始 if(index==0){ this.append_left(node) }else{ for(let i=0; i<index-1; i++){ // 调整指针所指，即调整引用对象位置 pointer = pointer.next; // 逐个指向下一个结点，直至`pointer`指向被索引结点的前一个结点 } node.next = pointer.next; // 先收小弟 pointer.next = node // 再上位 this.length = this.length + 1; // 更新结点长度 } } } p_insert(pointer:Lnode):void{ /** * 在指链表指针所指结点的后面插入一个新的结点 * @param pointer {Lnode} 模拟指针，实际上也是一个结点。 */ } 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; // 指向头结点的指针（实际上是引用） if(index==0){ nodes.next = this.head.next; // 先收小弟（接纳原先头节点的后继） this.head = nodes; // 再上位（替换到原先头节点的位置上） }else{ for(let i=0; i<index-1; i++){ pointer = pointer.next; // 指向链表中的下一个结点，直至指向被替换结点的前一个结点 } nodes.merge(pointer.next) // 先收小弟，即新结点接纳被替换结点的后继 pointer.next = nodes; // 再上位，即被替换结点的前一个结点的后继指向新结点 } 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`的某个结点及其之后的所有结点 * @param index {number} 结点索引号，该索引号指示结点及其之后全部结点都将从链表中删除 */ 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{ if(index==0){this.clear() }else{ let pointer:Lnode = this.head; for(let i=0; i<index-1; i++){ pointer = pointer.next; // 指向下一个，直至指向索引结点的前一个 }; pointer.next = null; // 通过清空被索引结点的前一个结点的后继指针，将被索引系欸但及其后从链表删除 } } }else if(typeof(index)=="object"){ /** * 删除索引号从`a`（包含）到`b`（包含）的一段结点 * 允许`a`和`b`任意一个索引值更大，即不区分区间起始大小。 * @param index {number[]} 包含两个索引值范围的数组。该范围内的所有结点都将从链表中删除。 */ let a:number = index[0]; let b:number = index[1]; if(a>b){ // 不论先前哪一个索引值更大，始终转换为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; // 引用头节点作为指针 for(let i=0; i<a-1; i++){ // 处理结点范围为：[0:a-1] pointer = pointer.next; // 以`pointer`为指针，逐步指向下一个结点，直至指向索引a结点的前一个结点 }; for(let i=0; i<b-a+1; i++){ // 处理结点范围为：[a:b] pointer.next = pointer.next.next // 以`pointer.next`为指针，逐步指向下一个结点，直到跳过中间`b-a+1`个结点 }; // 到此为止，后面[b+1,]的结点也是自动挂着的，无需再处理 } } 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; // 创建指针（对象引用） for(let i=0; i<index-1; i++){ pointer = pointer.next; // 指向下一个，直至指向被索引结点的前一个结点 } pointer.next = pointer.next.next // 跳过被索引结点以实现删除之 } } } pop():Lnode{ /** * 弹出最右边的一个结点并返回 * @returns node {Lnode} 原链表最右侧的一个结点 */ if(this.head==null){throw "PopEmptyListError: Unable to pop up node from an empty linked list.";} else if(this.length==1){ let last:Lnode = this.head; this.head = null; return last } else{ let pointer = this.head; // 创建指针（对象引用） while(pointer.next.next!=null){ pointer = pointer.next; // 指向下一个，直至指向倒数第二个结点 }; let last:Lnode = pointer.next pointer.next = null this.length = this.length - 1; if(this.length==0){this.head=null}; return last; } } 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; } } merge(list:LinkList):void{ /** * 实现两个链表的合并 * 传入另外一个链表，将这个新传入的链表挂载到本链表的后边 * @param list{LinkList} 将要合并到本链表的一个新链表 */ let pointer:Lnode = this.head; // 指向本链头链表指针，实际上是对链表结点对象的引用 while(pointer.next!=null){ // 先将指针移动到本链表的尾部 pointer = pointer.next; } pointer.next = list.head; // 将本链表的链尾结点指向新链表的链头结点 } 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 } }
4. 两个链表的合并
要合并两个链表无非是将一个链表的尾元结点的后继指针由null改为指向另外一个链表的首元结点。
在上面的新代码中，我们已经包含了两个链表合并的merge()方法。为了方便起见，将它拿出来单独展示在此：
merge(list:LinkList):void{ /** * 实现两个链表的合并 * 传入另外一个链表，将这个新传入的链表挂载到本链表的后边 * @param list{LinkList} 将要合并到本链表的一个新链表 */ let pointer:Lnode = this.head; // 指向本链头链表指针，实际上是对链表结点对象的引用 while(pointer.next!=null){ // 先将指针移动到本链表的尾部 pointer = pointer.next; } pointer.next = list.head; // 将本链表的链尾结点指向新链表的链头结点 }
代码测试：
let list_1 = new LinkList([1,2,3]); // 构造第1个链表 let list_2 = new LinkList([4,5,6]); // 构造第2个链表 list_1.merge(list_2); // 用第1个链表吸收第二个链表的元素 console.log(list_1.toArray());
Out[]:
[ Lnode { empty: false, data: 1, next: null }, Lnode { empty: false, data: 2, next: null }, Lnode { empty: false, data: 3, next: null }, Lnode { empty: false, data: 4, next: null }, Lnode { empty: false, data: 5, next: null }, Lnode { empty: false, data: 6, next: null } ]
可以看到，第二个链表中的结点元素被依序并入了第一个链表中。
