前言
上次讲解了单向链表的原理《Java实现单向链表功能》，今天拓展一下实现链表的翻转。
下面直接上代码。
链表初始化
public class LinkedArray<T extends Number>{
//链表的头节点
private Entry<T> head;
//节点实体类
static final class Entry<T>{
//记录当前节点的下一个节点
Entry<T> next;
T t;
public Entry(T t) {
// TODO Auto-generated constructor stub
this.t = t;
}
}
}
添加节点
public void add(T t) {
//根据参数创建一个节点
Entry<T> entry = new Entry<T>(t);
//当链表为空时，记录head节点
if(head == null) {
head = entry;
}else {
//节点移动，并且赋值，保持head节点为新增加的entry
entry.next = head;
head = entry;
}
}
添加的过程结合代码注释和下面图片：
添加过程
链表反转
public void reverse() {
///记录current的节点是head大的下一个节点。
Entry<T> current = head.next;
//切断head.next指向current，（当前的head变为链表的尾，所以next为空）
head.next = null;
while(current != null) {
//记录currentNext的节点是currentNext大的下一个节点。
Entry<T> currentNext = current.next;
//current.next反方向指向以前的节点
current.next = head;
//移动head和current指针，到后面head重新成为头节点
head = current;
current = currentNext;
}
}
翻转的过程结合代码注释和下面图片：
翻转过程.png
整个链表的插入以及翻转就实现了，但是要注意的是链表中元素的顺序是按照插入的顺序，并不是按照元素实际数值的大小排序。下面拓展实现插入按照排序。
自然数序插入
本文只讨论Number类型的顺序排列
public void addByOrder(T t) {
//根据参数创建一个节点
Entry<T> entry = new Entry<T>(t);
//当链表为空时，记录head节点
if(head == null) {
head = entry;
}else {
//从head开始，记录上个节点，
//current是当前节点，previous为current的上一个节点
Entry<T> current = head;
Entry<T> previous = head;
//遍历整条链表，直到当前current节点为空(链表已经到尾部)
//或者插入的树数值比当前current大
while(current != null && t.doubleValue()>current.t.doubleValue()) {
//节点移动
previous = current;
current = current.next;
}
//当前链表只有head一个节点，
//并且传入大的数值比head小(因为current == previous，current节点并没有移动)
if(current == previous) {
entry.next = head;
head = entry;
}else {
//找到节点的位置，在previous和current的中间插入
previous.next = entry;
entry.next = current;
}
}
}
添加的过程结合代码注释和下面图片：
自然顺序插入.png
运行结果
主函数随机输入10个数字,测试排序与不排序的情况。
public static void main(String[] args) {
// TODO Auto-generated method stub
add();
System.out.println("-------------分割线-----------");
addByOrder();
}
private static void add() {
LinkedArray<Number> list = new LinkedArray<>();
list.add(3);
list.add(4);
list.add(8);
list.add(6);
list.add(9);
list.add(2);
list.add(1);
list.add(5);
list.add(0);
list.add(7);
System.out.println(list.findAll());
list.reverse();
System.out.println(list.findAll());
}
private static void addByOrder() {
LinkedArray<Number> list = new LinkedArray<>();
list.addByOrder(3);
list.addByOrder(4);
list.addByOrder(8);
list.addByOrder(6);
list.addByOrder(9);
list.addByOrder(2);
list.addByOrder(1);
list.addByOrder(5);
list.addByOrder(0);
list.addByOrder(7);
System.out.println(list.findAll());
list.reverse();
System.out.println(list.findAll());
}
运行结果
结果.png
总计
上面讨论了插入节点，顺序插入节点和翻转的功能。链表需要重点理解清楚指针的移动。更多的单向链表功能请参考《Java实现单向链表功能》
