java数据结构和算法——单链表（Linked List）单链表反转（反转后链表的结构是原始链表顺序的倒序）的应用示例

一、单链表反转的思路分析示意图

二、单链表反转的实现步骤的分解图

三、单链表反转的代码示例

注意：反转后的链表结构是原始链表顺序的倒序

1、定义一个人员节点类，每一个PersonNode对象就是一个节点

package com.rf.springboot01.dataStructure.singleLinkedList;

/**
 * @description: 定义一个人员节点类，每一个PersonNode对象就是一个节点
 * @author: xiaozhi
 * @create: 2020-07-15 16:44
 */
public class PersonNode {

    public int num;//编号
    public String name;//名称
    public String aliasName;//别名
    public PersonNode next;//指向下一个节点

    //构造器
    public PersonNode(int num, String name, String aliasName) {
        this.num = num;
        this.name = name;
        this.aliasName = aliasName;
    }
    //重写toString方法
    @Override
    public String toString() {
        return "PersonNode{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", aliasName='" + aliasName + '\'' +
                '}';
    }
}

2、创建一个单链表管理人员节点

package com.rf.springboot01.dataStructure.singleLinkedList;


/**
 * @description: 创建一个单链表管理人员节点
 * @author: xiaozhi
 * @create: 2020-07-16 22:04
 */
public class SingleLinkedList {
    //先初始化一个头结点，头节点位置固定，不存放任何数据，作用是表示链表的头节点
    private PersonNode head =new PersonNode(0,"","");

    public PersonNode getHead() {
        return head;
    }

    //在链表的指定位置添加节点数据
    public void addByNum(PersonNode personNode){
        PersonNode temp=head;
        boolean flag=false;//插入的编号是否存在，默认不存在
        while(true){
            if(temp.next==null){//已经在链表的尾部
                break;
            }
            if(temp.next.num >personNode.num){//找到位置，在temp后添加
                break;
            }
            if(temp.next.num==personNode.num){//编号已经存在，不能添加
                flag=true;
                break;
            }
            temp=temp.next;//后移，遍历
        }
        if(flag){
            System.out.printf("添加的人员编号%d已经存在，不能添加\n",personNode.num);
        }else{
            //添加数据到链表中，temp后的位置
            personNode.next=temp.next;
            temp.next=personNode;
        }
    }
    
    //显示链表
    public void show(){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个临时变量来遍历
        PersonNode temp=head.next;
        while(true){
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将temp向后移动
            temp = temp.next;
        }
    }

    /** 
    * @Description: 单链表的反转
    * @Param:  PersonNode
    * @Author: xz
    * @Date: 2020/7/21 9:49
    */
    public static void reverseLinkedList(PersonNode head){
        //如果当前链表为空或者只有一个链表节点，直接返回
        if(head.next ==null || head.next.next==null){
            return;
        }
        //定义一个反转节点的头节点reverseHead
        PersonNode reverseHead=new PersonNode(0,"","");
        //定义一个临时节点,用来遍历原始的链表
        PersonNode temp =head.next;
        //定义一个临时节点的下一个节点
        PersonNode tempNext=null;
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端。
        while(temp !=null){
            tempNext=temp.next;//先保存临时节点的下一个节点
            temp.next=reverseHead.next; //将临时节点的下一个节点指向新的链表的最前端
            reverseHead.next=temp;//将temp链接到新的链表上
            temp=tempNext;//将临时节点后移
        }
        head.next=reverseHead.next;//将head.next指向reverseHead.next，实现单链表的反转
    }
  
}

3、定义一个测试类

package com.rf.springboot01.dataStructure.singleLinkedList;
/**
 * @description:
 * @author: xiaozhi
 * @create: 2020-07-16 22:05
 */
public class SingleLinkedListTest {
    public static void main(String[] args) {
        //创建节点
        PersonNode personNode1 = new PersonNode(1, "张三", "小张");
        PersonNode personNode2 = new PersonNode(2, "李四", "小李");
        PersonNode personNode3 = new PersonNode(3, "王五", "小王");
        PersonNode personNode4 = new PersonNode(4, "赵二", "小赵");

        //添加链表节点数据
        SingleLinkedList s3 = new SingleLinkedList();
        s3.addByNum(personNode1);
        s3.addByNum(personNode4);
        s3.addByNum(personNode2);
        s3.addByNum(personNode3);

        //显示所有链表节点
        System.out.println("原始链表节点数据============");
        s3.show();

        System.out.println("反转后的链表节点数据============");
        SingleLinkedList.reverseLinkedList(s3.getHead());
        //显示所有链表节点
        s3.show();

    }
}

4、输出结果如下：