TypeScript数据结构与算法专题 -
[单链表4] 单链表节点的`两-两`反转的实现
1 交换数据法实现链表结点的两两反转
这种方法只需要将相邻的链表的数据域所存储的内容以每两个一组的形式进行互换，实际上并不需要改变改变链表中任何结点的连接关系。过程可以用下图来表示：
这里我们采用了双指针，前一个指针和后一个指针分别指向一组中的前后两个结点。从一组到下一组的过程就是一组中的两个指针同时每向后移动两个结点的过程。
其实现代码如下：
swapDataBy2():void{ /**采用交换数据法以每2个结点一组翻转相邻元素 */ let pointer_pre: Lnode = this.head; // 从指向第1个结点开始 let pointer_next: Lnode = this.head.next; // 从指向第2个结点开始 if(this.length %2 ==0){ // 恰好偶数个结点 while(pointer_next.next!=null){ // 交换数据 let data = pointer_pre.data; // 暂存前一个结点的数据 pointer_pre.data = pointer_next.data; // 前一个结点接收后一个结点的数据 pointer_next.data = data; // 后一个结点接收（暂存的）前一个结点的数据 // 移动指针 pointer_pre = pointer_pre.next.next; pointer_next = pointer_next.next.next; } }else{ // 奇数个结点 while(pointer_next.next.next!=null){ // 交换数据 let data = pointer_pre.data; pointer_pre.data = pointer_next.data; pointer_next.data = data; // 移动指针 pointer_pre = pointer_pre.next.next; pointer_next = pointer_next.next.next; } } // 最后一组 let data = pointer_pre.data; pointer_pre.data = pointer_next.data; pointer_next.data = data; }
代码测试
现在我们将该方法添加到之前写的链表类中，（之前的详细代码见上一篇博客《链表的合并以及对TypeScript链表实现中的一些问题总结与改进》中的完整代码部分）分别测试一下对含有奇数和偶数个结点的链表实现两个一组翻转的效果，为了方便查看，我们依然是转化为结点数组后输出。
【text1】奇数个结点分组翻转
let list = new LinkList([1,2,3,4,5,6,7,8,9]); list.swapDataBy2() console.log(list.toArray());
Out[]:
[ Lnode { empty: false, data: 2, next: null }, Lnode { empty: false, data: 1, next: null }, Lnode { empty: false, data: 4, next: null }, Lnode { empty: false, data: 3, next: null }, Lnode { empty: false, data: 6, next: null }, Lnode { empty: false, data: 5, next: null }, Lnode { empty: false, data: 8, next: null }, Lnode { empty: false, data: 7, next: null }, Lnode { empty: false, data: 9, next: null } ]
【text】偶数个结点分组翻转
let list = new LinkList([1,2,3,4,5,6,7,8,9,10]); list.swapDataBy2() console.log(list.toArray());
Out[]:
[ Lnode { empty: false, data: 2, next: null }, Lnode { empty: false, data: 1, next: null }, Lnode { empty: false, data: 4, next: null }, Lnode { empty: false, data: 3, next: null }, Lnode { empty: false, data: 6, next: null }, Lnode { empty: false, data: 5, next: null }, Lnode { empty: false, data: 8, next: null }, Lnode { empty: false, data: 7, next: null }, Lnode { empty: false, data: 10, next: null }, Lnode { empty: false, data: 9, next: null } ]
2 改变结点引用关系实现链表结点的两两反转
接下来我们采用另一种方法来完成两两翻转的目的。实际上，在1.1节中的方法，我们的各结点之间的链接关系始终是保持不变的，并没有真正调整过结点的连接方式，改变的只是各个结点的数据。而接下来我们这一种方式才是真正从结点的关系上实现反转。这次，我们打算使用一个指针，从原链表的头节点开始，依次以2个结点向链表的尾元结点方向移动。
我们期待的过程大概是这样子的：
在这种实现中有一个十分需要注意的地方。
假设变量p是对某一个结点对象的引用（指向某个结点对象），如果你在代码中将引用另外一个对象的变量赋值给变量p并不会对变量p所引用的对象做任何改变，而只会进行引用的传递，即让p引用到另外一个变量索引用的相同一个对象。
如果p是一个结点对象的引用，你能通过p修改的只不过是这个对象所拥有的一些属性，如p.next，而绝不能觊觎通过对p赋值使得其它引用到这个对象的引用发生改变。
这意味着，你要通过引用来更改结点需要引用到被更改结点的前驱结点。因此在实现时要注意区分是通过引用修改对象还是直接修改对象本身。
基于以上原因，我们实际上不能直接由上图的过程完成相邻元素的翻转。为了方便起见，我这里采用了一个我称之为虚拟挂载点的空结点，它指向原链表头节点，相当于头节点指针。而接下来在实行翻转时，我们只需要一个指针，初始指向虚拟挂载点，之后每次后指两个结点。
代码实现如下：
reverseBy2():void{ /** * 将链表中的结点每2个一组进行翻转 */ // 只组要考虑结点个数多于或等于2个的情况 if(!(this.head==null || this.head.next==null)){ let pre = new Lnode(); // 虚拟挂载点 pre.next = this.head; // 虚拟挂载点后继指向从点结点开始的所有结点 let pointer:Lnode = pre; // 指针初始指向虚拟挂载点 while(pointer.next!=null && pointer.next.next!==null){ let node:Lnode = pointer.next; pointer.next = pointer.next.next; node.next = pointer.next.next; pointer.next.next = node; pointer = pointer.next.next; } this.head = pre.next; // 从虚拟挂载点卸载 } }
代码测试：
let list = new LinkList([1,2,3,4,5,6,7,8,9,10]); list.reverseBy2() console.log(list.toArray());
Out[]:
[ Lnode { empty: false, data: 2, next: null }, Lnode { empty: false, data: 1, next: null }, Lnode { empty: false, data: 4, next: null }, Lnode { empty: false, data: 3, next: null }, Lnode { empty: false, data: 6, next: null }, Lnode { empty: false, data: 5, next: null }, Lnode { empty: false, data: 8, next: null }, Lnode { empty: false, data: 7, next: null }, Lnode { empty: false, data: 10, next: null }, Lnode { empty: false, data: 9, next: null } ]
可以看到，顺利达到了两个一组进行翻转的目的。
喜欢的话记得来个一赞三连鼓励哦(＾Ｕ＾)ノ~ＹＯ感激不尽
