基于Java实现单链表反转的多种方法

对于单链表不熟悉的可以看一下基于Java实现单链表的增删改查

一、原地反转

1、新建一个哨兵节点下一结点指向头结点
2、把待反转链表的下一节点插入到哨兵节点的下一节点
反转之前的链表：1–>2–>3–>4>–>5
加入哨兵节点：dummp–>1–>2–>3–>4>–>5
原地反转：
定义：prev=dummp.next; pcur=prev.next;
prev.next=pcur.next;
pcur.next=dummp.next;
dummp.next=pcur;
pcur=prev.next;

public Stu_node reverse_list(Stu_node head){
   
        if (head.next==null ||head.next.next==null)
            return null;
        Stu_node dump = new Stu_node(-1," ");
        dump.next=head;
        Stu_node prev = dump.next;
        Stu_node pcur = prev.next;
        while(pcur!=null){
   
            prev.next=pcur.next;
            pcur.next=dump.next;
            dump.next=pcur;
            pcur=prev.next;
        }
        return dump.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、新建链表头结点插法

二、新建链表头结点插法：

新建一个头结点，遍历原链表，把每个节点用头结点插入到新建链表中。最后，新建的链表就是反转后的链表。

public Stu_node reverse_list1 (Stu_node head){
   
        //新建一个新的链表的头结点
        Stu_node dump = new Stu_node(-1," ");
        Stu_node pcur = head;
        //遍历待反转链表，头结点插入到新的链表中
        while(pcur!=null){
   
            Stu_node pnext = pcur.next;
            pcur.next = dump.next;
            dump.next=pcur;
            pcur
1
2
3
4
5
6
7
8
9
10
11