链表应用-头插法反转链表

思路：

1.先定义一个节点reverseHead = new HeroNode()

2. 从头到位遍历链表，每遍历一个元素就摘下该元素然后放在链表reverseHead的最前端

3. 用原来的链表替换新的链表：head.next = reverseHead.next

   图示意：

使用头插法之后：

代码实现：

前提：

//定义一个heroNode
class HeroNode{
    //编号
    public int no;
    //英雄名字
    public String name;
    //英雄昵称
    public String nickName;
    //指向的下一个英雄
    public HeroNode next;

    public HeroNode(int no,String name,String nickName){
        this.no = no;
        this.nickName = nickName;
        this.name = name;
    }

    @Override
    public String  toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

翻转链表思路：

/**
     * 反转链表：头插法
     * 思路：先定义一个节点reverseHead = new HeroNode()
     * 从头到位遍历链表，每遍历一个元素就摘下该元素然后放在链表reverseHead的最前端
     */
    public void reverseLinkedList(){
        HeroNode reverseHead = new HeroNode(0,"","");
        //判空
        if(head.next ==null){
            System.out.println("链表为空");
            return;
        }
        //定义辅助变量
        HeroNode temp = head.next;
        //遍历链表
        while (temp!=null){
            //把这个节点摘下，然后插入反转链表最前面
            head.next = temp.next;
            temp.next =null;
            //把这个值插入到反转链表头部
            if(reverseHead.next!=null){
                temp.next = reverseHead.next;
                reverseHead.next = temp;
            }else{
                reverseHead.next = temp;
            }
            //后移,因为temp节点已经被摘掉了，所以head节点下一个节点就是第二个节点
            temp = head.next;
        }
        //得到了反转链表reverseHead,然后替换原来的链表
        head.next = reverseHead.next;
        //遍历head
        HeroNode temp1 = head.next;
        while (temp1!=null){
            System.out.println(temp1);
            temp1 = temp1.next;
        }
    }

测试demo:

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        HeroNode heroNode1 = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode3 = new HeroNode(3,"吴用","智多星");
        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");
        HeroNode heroNode5 = new HeroNode(5,"张飞","黑旋风");
        singleLinkedList1.addNodeInOrder(heroNode1);
        singleLinkedList1.addNodeInOrder(heroNode3);
        singleLinkedList1.addNodeInOrder(heroNode2);
        singleLinkedList1.addNodeInOrder(heroNode5);
        singleLinkedList1.addNodeInOrder(heroNode4);
        singleLinkedList1.showNode();
        System.out.println("===========翻转链表==============");
        singleLinkedList1.reverseLinkedList();
    }
}

结果：

===========翻转链表==============
HeroNode{no=5, name='张飞', nickName='黑旋风'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=1, name='宋江', nickName='及时雨'}