[单链表5] 单链表节点的`任意分组反转`实现
李俊才
CSDN：jcLee95
邮箱：291148484@163.com
专题目录：https://blog.csdn.net/qq_28550263/article/details/115718216
【导读】： 在上一篇博文《单链表节点的
两-两反转的实现》（点击链接进行跳转）中，我们采用了 “交换数据法” 和 “改变结点引用关系” 两种方法来实现以2个结点为一组对链表进行分组反转。本文我们将进一步加大难度，对链表以任意指定参数k个为一组，对链表进行分组反转。
->点我跳转：如果你不是很理解什么是任意k结点个一组反转可以先看一下运行结果
0. 对上一篇及之前博文代码的删改
在上一篇以及之前的代码中实现单链表时，我们还真没有用所谓头指针，同样实现了相应的结构与功能。由于在TypeScript中同样是没有指针，这使得我们如果要更改头结点线的十分麻烦，并且部分方法我们是通过使用一个结点来作为挂载头节点的挂载点，通过引用该挂载点来操作头结点的。实际上该挂载点就起到了头指针的功能。因此我们有必要设定一个头指针，这个指针是同一个结点模拟的。结点挂载头指针上，这样对于链表所有结点的操作具有统一性。在删除掉实用性功能不大或者被本文包含的两两翻转结点，以及其它重复实现的功能之后，我们给出新的代码如下：
// 这里提供一个由头指针的链表的实现方法
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():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; // 从头结点开始
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(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
}
count(x:any):number{
/**
* 返回链表中结点的值域存储内容与x内容相同的结点的个数
* @param x {any} 用于比较的数据
*/
let counter = 0;
let pointer:Lnode = this.head.next;
while(pointer){
if(pointer.data == x){
counter++ // 技术
}
pointer = pointer.next;
}
return counter
}
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{
/**
* 替换指定索引处结点的数据
* 该方法不会改变结点的连接关系
*/
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{
/**
* 替换指定索引处的结点
*/
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(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.next==null){throw "PopEmptyError: Unable to pop up node from an empty linked list.";}
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