TypeScript数据结构与算法专题 -
[单链表5] 单链表节点的`任意分组反转`实现
0. 对上一篇及之前博文代码的删改
如果使用C语言实现，则头指针和头结点有所不同，若头指针为head则头节点是*head。如果链表带有头节点则头指针指向头结点、头节点的指针域指向首元结点。也就是说C语言实现的链表中头结点可能并不是首元结点，而首元结点为其后继结点，头节点的作用是"方便插入、删除等运算的实现"。如果链表没有头节点，则头指针直接指向首元结点。
不过TypeScript中是没有指针的概念，我们也没有必要像C语言中那样区分头指针与头节点。但是与C语言中采用头节点以保持链表操作的一致性一脉相承，我们也设置一个头结点，即：
| 为了“简化链表的插入和删除操作，并统一空表和非空表的操作，决定在链表的链头设置头结点。这样无论是在链表的首元结点处插入还是在链表的中间或者尾部插入，都能够统一处理。 |
在删除掉实用性功能不大或者被本文包含的两两翻转结点，以及其它重复实现的功能之后，我们给出新的代码如下：
// 这里提供一个由头指针的链表的实现方法 class Lnode{ /** * 链表结点类，结点是构成链表的基础单元。 * @class Lnode * @constructor * @param next {Lnode} 指向下一结点的指针 * @param data {string | number} 结点的数据。 * @param empty {boolean} 结点是否为空的标记。 */ next: Lnode | null; // 结点类型（Lnode）的nest也是结点类型Lnode，undefined和null是任意类型的子类型也可以不写 data: any; empty:boolean; constructor(); constructor(data); constructor(data?:any){ if(data!=undefined){ // 非空结点 this.data = data; this.next = null; this.empty = false }else{ // 空结点，即值构建结点对象但实际上不存在结点 this.data = null; this.next = null; this.empty = true; } } } export class LinkList{ /** * 单链表类 * @class LinkList * @constructor * @param head {Lnode} 实际上用于替代头结点 * @param length {number} 链表的长度 */ head: Lnode; // 头指针，其next挂载链表的第一个结点。实际上也是一个结点 length: number; // 链表所容纳结点的个数 constructor(); // 重载构建空链表 constructor(datas:any[]); // 重载传入一组数据作为元素构建非空链表 constructor(datas?:any[]){ /**初始化 */ this.head = new Lnode(); if(datas==undefined){ this.head.next = null; // head.next 为头指针，指向首元结点 this.length = 0; // 初始化链表长度 }else{ for(let i=0; i<datas.length; i++){ this.append(datas[i]) } this.length = datas.length; // 指定一组数据初始化则初始后长度为这组数据元素的个数 } } is_empty(){ /** * 判断链表是否为空 * 只需要判断头结点是否为空，若头结点为空则为空链表，否则不是。 * @return {Boolean} true:链表为空; false:链表非空。 */ if(this.head.next == null){ return true; }else{ return false; } } top():any{ /** * 获取链表头结点的数据域内容 */ return this.head.next.data; } top_node():Lnode{ /** * 获取链表头结点 */ let node = this.head.next; node.next = null; return node; } clear(){ /** * 清空链表，只要把头结点干废，整个链表直接就清空了 */ this.head.next = null; this.length = 0; } append(elm: any):void{ /** * 用数据构成新结点插入单链表尾部 * @param elm {any} 需要插入链表尾部的新结点 */ if(this.head.next == null){ // 没有头结点 this.head.next = new Lnode(elm); this.length = this.length + 1; }else{ let pointer = this.head.next; // 指向头节点 while(pointer.next != null){ pointer = pointer.next } pointer.next = new Lnode(elm) } } append_node(node: Lnode):void{ /** * 将新结点挂载到链表尾部 * @param node {Lnode} 需要插入链表尾部的新结点 */ if(this.head.next == null){ // 没有头结点 this.head.next = node; this.length = this.length + 1; }else{ let pointer = this.head.next; // 指向头节点 while(pointer.next != null){ pointer = pointer.next } pointer.next = node } } append_left(elm: any):void{ /** * 用数据构成新结点插入单链表头部 * @param elm {any} 需要插入链表尾部的新结点 */ if(this.head == null){ this.head.next = new Lnode(elm); // 若为空链表，直接将链表头设置为该结点 this.length = this.length + 1; // 增加结点长度 }else{ // 先将新结点的`next`指向原第一个结点 let node = new Lnode(elm); node.next = this.head.next; // 再将`head`指向新的结点 this.head.next = node; this.length = this.length + 1; // 增加结点长度 } } append_node_left(node: Lnode){ /** * 将一个新结点插入到链表首部 * @param node {Lnode} 要从左侧也就是链头插入的新结点 */ if(this.head.next == null){ this.head.next = node; // 若为空链表，直接将链表头设置为该结点 this.length = this.length + 1; // 增加结点长度 }else{ // 先将新结点的`next`指向原第一个结点 node.next = this.head.next; // 再将`head`指向新的结点 this.head.next = node; this.length = this.length + 1; // 增加结点长度 } } get_node(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.next; // 从头结点开始 for(let i=0; i<index;i++){ pointer = pointer.next; // 逐个指向下一个结点 }; pointer.next = null; // 斩断后继 return pointer; }; }; get(index: number):any{ /** * 索引结点地数据 * @param index {number} 索引号 * @return data {any} 链表中与索引号对应地节点地数据域内容 */ return this.get_node(index).data }; index(x:any):number{ /** * 返回链表中第一个数据域 x 的元素的零基索引 * @param x {any} 用于寻找索引的数据 */ let pointer: Lnode = this.head.next; // 从引用（指向）第一个结点开始 let index = 0; // 当前考察结点的索引号，从0开始计算（所谓零基） while(pointer.data!=x){ // 如果当前引用结点数据域的值不是给定值 pointer = pointer.next; // 同样的故事给下一个结点 index++; // 索引号也变成下一个结点的索引号 } return index } insert(index:number, node:Lnode):void{ /** * 在链表的第`index`个节的位置挂载新的结点`node`，其中从结点为`index = 0`开始编号 * 也就是说，新的结点索引号将为`index`，而这个结点将挂载到索引号为`index-1`的结点后面 * * @param index {number} 新结点插入的索引号 * @param node {Lnode} 要插入的新结点 */ 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_node_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; // 更新结点长度 } } } to_array_node():Lnode[]{ /** * 获取链表结点依次构成的数组 * @returns elem {Lnode[]} 以此装载了被遍历到的所有结点（这里其中每个结点都是孤立、干掉next的） */ let elm: Lnode[] = []; // 准备好用于容纳所有的结点 let pointer:Lnode = this.head.next; // 挂载操作一开始时指针指向头部结点、 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; } } to_array():any[]{ /** * 获取链表结点依次构成的数组 * @returns elem {Lnode[]} 以此装载了被遍历到的所有结点（这里其中每个结点都是孤立、干掉next的） */ let elm: Lnode[] = []; // 准备好用于容纳所有的结点 let pointer:Lnode = this.head.next; // 挂载操作一开始时指针指向头部结点、 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(pointer.data); } pointer = pointer.next; // 指向后继 } elm.push(pointer.data); // 最后一个元素 return elm; } } replace(index: number, data:any):void{ /** * 替换指定索引处结点的数据 * 该方法不会改变结点的连接关系 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} let pointer:Lnode = this.head; let ct: number = 0; while(ct < index){ // 指针逐渐指向被修改数据的前一结点 pointer = pointer.next; ct++; }; pointer.next.data = data; // 修改结点的数据域 }; replace_node(index: number, node:Lnode):void{ /** * 替换指定索引处的结点 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} let pointer:Lnode = this.head; let ct: number = 0; while(ct < index){ pointer = pointer.next; ct++; }; node.next = pointer.next.next; pointer.next = node; }; drop(index1: number); drop(index1: number, index2: number); drop(index1: number, index2?: number){ if(this.head==null){throw "EelEmptyListError: Unable to pop up node from an empty linked list."; }else{ if(index2==undefined){ /** * 给定一个索引号`index1`时 * 删除索引号为`index1`的某个结点及其之后的所有结点 * @param index {number} 结点索引号，该索引号指示结点及其之后全部结点都将从链表中删除 */ if(index1<0){throw "ValueError: Index must be a positive integer!"} else if(index1+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} if(index1==0){ this.clear() }else{ let pointer:Lnode = this.head.next; for(let i=0; i<index1-1; i++){ pointer = pointer.next; // 指向下一个，直至指向索引结点的前一个 }; pointer.next = null; // 通过清空被索引结点的前一个结点的后继指针，将被索引系欸但及其后从链表删除 }; }else{ /** * 给定两个索引号`index1`和`index2`时 * 删除索引号从`a`（包含）到`b`（包含）的一段结点 * 允许`a`和`b`任意一个索引值更大，即不区分区间起始大小。 * @param index {number[]} 包含两个索引值范围的数组。该范围内的所有结点都将从链表中删除。 */ // if(index1==index2){this.del(index1)} if(index1==index2){this.del(index1)} else if(index1+1 > this.length || index2+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else if(index1<0 || index2<0){throw "ValueError: Index must be a positive integer!"} else{ let a:number = index1; let b:number = index2; if(a>b){ // 不论先前哪一个索引值更大，始终转换为a更小、b更大 a = index2; b = index1; } let pointer:Lnode = this.head; // 引用头节点 if(a!=0){ for(let i=0; i<a; 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{ for(let i=0; i<b+1; i++){ // 处理结点范围为：[a:b] pointer.next = pointer.next.next // 以`pointer.next`为指针，逐步指向下一个结点，直到跳过中间`b-a+1`个结点 }; // 到此为止，后面[b+1,]的结点也是自动挂着的，无需再处理 } } } } }; del(index:number){ /** * 删除索引号为`index`的某个结点，保留其后继结点 * @param index {number} 将被删除的结点的索引号 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(this.head.next==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.next; // 创建指针（对象引用） for(let i=0; i<index-1; i++){ pointer = pointer.next; // 指向下一个，直至指向被索引结点的前一个结点 }; pointer.next = pointer.next.next // 跳过被索引结点以实现删除之 }; }; }; pop():Lnode{ /** * 弹出最右边的一个结点并返回 * @returns node {Lnode} 原链表最右侧的一个结点 */ if(this.head.next==null){throw "PopEmptyListError: Unable to pop up node from an empty linked list.";} else if(this.length==1){ let last:Lnode = this.head.next; this.head.next = 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.next==null){throw "PopEmptyError: Unable to pop up node from an empty linked list." }else if(this.length==1){ let last:Lnode = this.head.next; this.head.next = null; return last }else{ let pointer = this.head.next; this.head.next = this.head.next.next; // 头结点右移一个 pointer.next = null; // 斩断后继联系 this.length = this.length - 1; // 更新链表长度 if(this.length==0){this.head=null}; return pointer; } } 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{ /** * 将原链表就地反转，不反返回何结果 * 该方法将会改变原链表 */ let pointer: Lnode = this.head; // 引用头指针 let h:Lnode = new Lnode(); // 新头指针 while(pointer.next){ // 若原链表还有结点 let node: Lnode = this.pop_left(); // 原链表弹出第一个结点 if(h.empty){ // 空 h.next = node; h.empty = false; }else{ node.next = h.next; h.next = node; } } this.head = h; } get_reverse():LinkList{ /** * 反转链表 * 原链表不变，返回反转后的新链表 */ let pointer: Lnode = this.head; // 引用头指针 let list: LinkList = new LinkList(); // 一个新链表 while(pointer.next){ // 逐个元素出来 let node: Lnode = this.pop_left(); list.append_left(node.data); } return list } }
1. 思路分析
通过链首弹出结点实现单链表分组反转
原理&步骤
为说明整个经过，我依旧采用了绘图的方式来辅助说明。如图PIC_1所示，一开始时有一个完整的链表，由于从链表头部结点能够以O(1)的实践复杂度获取结点，因此我们将从链表左边依次将结点“倒出”：
这样很快我们就能发现，如果按照结点“倒出来”的顺序，再依次从新结点链头部（左侧）插入一个结点，并且恰好与原来链表中的顺序是逆序关系的。
因此我们决定以每k个结点元素为一组获取从原链表“倒出来”结点构成结点链。这里需要指出，结点链对象是直接有节点类 class Lnode 的实例所构成，而并不是新的链表类 class Llist 实例。即出来的每k个结点，只要每次将已经出来的结点们作为一个整体挂在新结点的右侧就可以了，如图 PIC_3所示：
我们对每k个结点分为一组，但是如果全按照弹出原链表的顺序则将会导致全表的逆序。因此对于每一个节点组，我们需要将所有节点组的顺序倒着连接，实现最终的分组逆序。
整个过程和先完全反转链表后，在有k个一组按组逆序的结果和原理是一样的。因此可以有不同的代码书写方案。我们下面给出一种实现。
2. 代码实现
reverse_by_k(k: number):void{ /** * 将链表中的所有结点以k个为一组进行翻转 * @param k{number}分组的结点元素个数 */ let pointer: Lnode = this.head; // 引用头指针 let h:Lnode = new Lnode(); // 新头指针 let chain_p:Lnode = new Lnode(); // 用来引用每k个结点 let ct: number = 0; // 计数器 while(pointer.next){ // 若原链表还有结点 if(ct<k){ // 还不够k个结点，则增长子节点链 let node: Lnode = this.pop_left(); // 原链表弹出第一个结点 if(chain_p.empty){ chain_p.next = node; chain_p.empty = false; }else{ node.next = chain_p.next; chain_p.next = node; } ct++; if(this.length == 0){ // 针对最后一段的挂载 let pt:Lnode = h; while(pt.next){ pt = pt.next; } pt.next = chain_p.next } }else{ // 已经够k个结点，则将子结点挂载到新头，清空子结点链与计数器 if(h.empty){ h.next = chain_p.next; h.empty = false; }else{ let pt:Lnode = h; while(pt.next){ // 逐渐指向新子链表最后一个结点 pt = pt.next; } pt.next = chain_p.next } chain_p = new Lnode(); ct = 0; } } this.head = h; }
代码测试
import * as slist from "./LinkList/singly_linked_list_02" // 导入单链表模块2 let a = [1,2,3,4,5,6,7,8,9,10,11]; let k = 3; let list = new slist.LinkList(a); list.reverse_by_k(k) console.log("原始链表数据域为：",a); console.log("分组数为：",k); console.log("运行后的结果为：",list.to_array())
Out[]:
原始链表数据域为： [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 分组数为： 3 运行后的结果为： [3, 2, 1, 6, 5, 4, 9, 8, 7, 11, 10]
为了方便读者理解什么是k个一组反转，我在vscode运行了多组数据，可以参考之：
[Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [] 分组数为： 3 运行后的结果为： [] [Done] exited with code=0 in 1.043 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1 ] 分组数为： 3 运行后的结果为： [ 1 ] [Done] exited with code=0 in 1.012 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2 ] 分组数为： 3 运行后的结果为： [ 2, 1 ] [Done] exited with code=0 in 1.012 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1 ] [Done] exited with code=0 in 1.02 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 4 ] [Done] exited with code=0 in 1.01 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 5, 4 ] [Done] exited with code=0 in 0.999 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5, 6 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 6, 5, 4 ] [Done] exited with code=0 in 1.011 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5, 6, 7 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 6, 5, 4, 7 ] [Done] exited with code=0 in 1 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5, 6, 7, 8 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 6, 5, 4, 8, 7 ] [Done] exited with code=0 in 1.019 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 6, 5, 4, 9, 8, 7 ] [Done] exited with code=0 in 1.009 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 6, 5, 4, 9, 8, 7, 10 ] [Done] exited with code=0 in 1.001 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 6, 5, 4, 9, 8, 7, 11, 10 ] [Done] exited with code=0 in 1.012 seconds [Running] ts-node "f:\★★我的编讲2020--11-06\编程开发\TypeScript数据结构与算法\test.ts" 原始链表数据域为： [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] 分组数为： 3 运行后的结果为： [ 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10 ] [Done] exited with code=0 in 1.014 seconds
