单向链表反转(含图解)

article/2025/9/23 12:41:45

前言

上次讲解了单向链表的原理《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 stubthis.t = t;}}
}

添加节点

 public void add(T t) { //根据参数创建一个节点Entry<T> entry = new Entry<T>(t);//当链表为空时，记录head节点if(head == null) {head = entry;}else {//节点移动，并且赋值，保持head节点为新增加的entryentry.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());}