JAVA 实现单向链表的反转

 JAVA 实现带头结点的链表根据节点大小按顺序新增、修改、删除节点 该文章已实现单向链表的创建及遍历等操作。

那么在此基础上，如何实现单向链表的反转呢？

实现思路：

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

2. 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端.

3. 原来的链表的head.next = reverseHead.next

代码实现

上代码：在SingleLinkedList2.class中添加以下方法

 //反转链表
    public void reverseSingleList(HeroNode2 head2){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head2.next==null || head2.next.next==null){
            return;
        }
        HeroNode2 current = head2.next;
        HeroNode2 next =null;// 指向当前节点[current]的下一个节点
        HeroNode2 newhead = new HeroNode2(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
        while (current!=null){
            next = current.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            current.next = newhead.next;//将 current 的下一个节点指向新的链表的最前端
            newhead.next = current;//将 current 连接到新的链表上
            current = next;
        }
        //将 head.next 指向 reverseHead.next
        head2.next = newhead.next;
    }

 测试类：

public class SingleLinkedListDemo2 {

    public static void main(String[] args) {
        SingleLinkedList2 singleLinkedList = new SingleLinkedList2();
        HeroNode2 h1 = new HeroNode2(1,"AAA","A");
        HeroNode2 h2 = new HeroNode2(2,"BBB","B");
        HeroNode2 h3 = new HeroNode2(3,"CCC","C");
        HeroNode2 h4 = new HeroNode2(4,"DDD","D");

        singleLinkedList.addByOrder(h1);
        singleLinkedList.addByOrder(h3);
        singleLinkedList.addByOrder(h4);
        singleLinkedList.addByOrder(h2);
        singleLinkedList.list();

        singleLinkedList.reverseSingleList(singleLinkedList.getHeadNode());
        System.out.println("反转后的链表遍历~~~~~~~~~~~~");
        singleLinkedList.list();
 
    }

}

输出结果： 

HeroNode{no=1, name='AAA, nickName='A}
HeroNode{no=2, name='BBB, nickName='B}
HeroNode{no=3, name='CCC, nickName='C}
HeroNode{no=4, name='DDD, nickName='D}
反转后的链表遍历~~~~~~~~~~~~
HeroNode{no=4, name='DDD, nickName='D}
HeroNode{no=3, name='CCC, nickName='C}
HeroNode{no=2, name='BBB, nickName='B}
HeroNode{no=1, name='AAA, nickName='A}