单链表创建以及反转

头插法逻辑图（重点）

image.png

节点类

package listnode;

/**
 * 创建链表类
 */
public class ListNode{
    //链表的节点对象
    private int data;
    //存储下一个链表节点地址的属性
    private ListNode next;

    public ListNode(int data) {
        this.data = data;
    }

    public ListNode() {
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

    /**
     *   功能：创建一个链表，并返回头节点的地址
     * @param len 创建链表数据的长度
     * @return  返回头节点的地址
     */
    public ListNode create(int len){
        //初始化头节点，不带数据
        ListNode header=new ListNode(-1);
        header.next =null;
        //生成指定长度的随机数
        for (int i = 0; i <len ; i++) {
            //创建随机数
            int num=i+1;
            //创建一个节点对象
            ListNode temp=new ListNode();
            //存储数据
            temp.data=num;
            //是否第一次创建链表节点
            temp.next=header.next;
            header.next=temp;
        }
        return header;
    }
    /**
     * 遍历整个链表
     * @param header 链表中第一个节点的地址
     */
    public void show(ListNode header){
        while(header!=null){
            System.out.print(header.data+"->");
            //遍历下一个节点
            header=header.next;
        }
        System.out.println();
    }

    /**
     * 单链表头插法反转
     * @param listNode
     * @return
     */
    public  ListNode reverseList(ListNode listNode){
        //定义一个带头节点的
        ListNode phead = new ListNode(-1);
        //循环节点
        ListNode p = listNode;
        while(p!= null){
            //保存插入点之后的数据
            ListNode tempList = p.next;
            p.next = phead.next;//（参照头插法图）
            phead.next = p;
            p = tempList;
            show(phead);//输出每次的结果
        }
        return phead.next;
    }
}

main 函数

/**
 * @Description TODO
 * @Author feng
 * @Date 2020/10/16 15:42
 */
public class Main {
    public static void main(String[] args) {
        //创建链表对象
        ListNode listNode=new ListNode();
        //创建一个链表,并返回第一个节点的地址
        ListNode header=listNode.create(4);
        //遍历创建的链表，输出为0->4->3->2->1，因为事头插法，所以4在前面，0是头节点默认int值
        listNode.show(header.getNext());
        System.out.println("反转后");
        ListNode reverseNode = listNode.reverseList(header.getNext());
        listNode.show(reverseNode);
    }
}

输出效果：

image.png