人生设计师
这是系列文章，每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现，从而对常用的数据结构和
java集合有个大概的了解。当然实现没有java集合的实现那么复杂，功能也没有那么强大，但是可以通过这些简单的实现窥探到底层的一些共性原理。
一. 什么是单链表逆转?
我们知道,单链表的每个结点由两部分组成，一个数据域data和一个指向其后继结点的指针域next，最后一个结点的next域为空。单链表逆转就是将链表中各结点的next域指向它的前驱结点，原来第一个结点的next域为空，头结点head指向原来的最后一个节点。
单链表的逆转步骤描述如下：
1. 初始，设置p结点指向第一个结点，front结点指向p的前驱结点，q结点指向p的后继结点。
2. 循环中，将p的后继结点p.netx指向p的前驱结点front
3. 循环结束后已经实现逆转的单链表如下所示：
二. 算法实现
可逆转的单链表类是在前面文章已经实现的单链表SinglyLinkedList类的基础上增加了单链表逆转的功能，继承自SinglyLinkedList类。可逆转的单链表类ReverseSinglyLinkedList代码实现如下：
package org.light4j.dataStructure.linearList.linkList.reverse;
import org.light4j.dataStructure.linearList.linkList.Node;
import org.light4j.dataStructure.linearList.linkList.SinglyLinkedList;
/**
* 可逆转的单链表,继承自SinglyLinkedList
*
* @author longjiazuo
*/
public class ReverseSinglyLinkedList<E> extends SinglyLinkedList<E> {
public ReverseSinglyLinkedList() {
super();// 调用父类同参数的构造方法
}
/**
* 实现单链表逆转的方法
*/
public void reverse() {
Node<E> p = this.head;
Node<E> front = null;
Node<E> q = null;
while (p != null) {
q = p.next;// 设置q结点是p的后继结点
p.next = front;// 使p的后继结点指向其前驱节点
front = p;// front结点向后移动
p = q;// p结点向后移动
}
this.head = front;// 头结点指向front
}
}
代码解释：
① 设
p指向单链表的某个结点，front是p的前驱结点，那么使p的后继结点p.next指向p的前驱结点的语句是:p.next=front，但是如果将p的后继结点指向p的前驱结点，那么p和原来的后继结点之间的链接就断开了，于是我们需要声明一个q节点来记住p和原来后继结点之间的关系，使q=p.next。front，p，q这三个结点的引用同时沿着单链表向后移动。
三.测试
测试代码如下所示：
package org.light4j.dataStructure.linearList.linkList.reverse;
public class Test {
/**
* 测试
*
* @param args
*/
public static void main(String[] args) {
ReverseSinglyLinkedList<Integer> rslk = new ReverseSinglyLinkedList<Integer>();
for (int i = 1; i < 10; i++) {
rslk.add(0, new Integer(i));
}
System.out.println("单链表: " + rslk.toString());
rslk.reverse();
System.out.println("逆转后的单链表: " + rslk.toString());
}
}
运行结果如下所示：
四.源代码示例
公众号ID：longjiazuoA
未经允许不得转载：人生设计师 » 自己实现集合框架(四):可逆转单链表的实现