如何使用Java實現(xiàn)單鏈表的反轉(zhuǎn)？詳細(xì)方法總結(jié)！

學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)的小伙伴們，對單鏈表想來是并不陌生。本篇文章將為大家介紹幾種在 Java 語言當(dāng)中，實現(xiàn)單鏈表反轉(zhuǎn)的幾種方法，以下是具體內(nèi)容。

一、原地反轉(zhuǎn)

1、新建一個哨兵節(jié)點下一結(jié)點指向頭結(jié)點

2、把待反轉(zhuǎn)鏈表的下一節(jié)點插入到哨兵節(jié)點的下一節(jié)點

反轉(zhuǎn)之前的鏈表：1–>2–>3–>4>–>5

加入哨兵節(jié)點：dummp–>1–>2–>3–>4>–>5

原地反轉(zhuǎn)：

定義：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;
    }

二、新建鏈表頭結(jié)點插法

二、新建鏈表頭結(jié)點插法：

新建一個頭結(jié)點，遍歷原鏈表，把每個節(jié)點用頭結(jié)點插入到新建鏈表中。最后，新建的鏈表就是反轉(zhuǎn)后的鏈表。

public Stu_node reverse_list1 (Stu_node head){
        //新建一個新的鏈表的頭結(jié)點
        Stu_node dump = new Stu_node(-1," ");
        Stu_node pcur = head;
        //遍歷待反轉(zhuǎn)鏈表，頭結(jié)點插入到新的鏈表中
        while(pcur!=null){
            Stu_node pnext = pcur.next;
            pcur.next = dump.next;
            dump.next=pcur;
            pcur=pnext;
        }
        //新鏈表頭結(jié)點不是需要返回的數(shù)據(jù)，因此返回頭結(jié)點的下一節(jié)點
        return dump.next;
    }

三、利用棧結(jié)構(gòu)實現(xiàn)鏈表的反轉(zhuǎn)

由于棧結(jié)構(gòu)存儲數(shù)據(jù)是先進(jìn)后出（后進(jìn)先出）也可以通過棧達(dá)到反轉(zhuǎn)鏈表的目的。

 public Stu_node reverse_stack(Stu_node head){
        Stack<Stu_node> stack = new Stack<>();
        Stu_node temp = head;
        //鏈表入棧
        while(temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        //取出棧中的一個節(jié)點當(dāng)做新的鏈表的頭結(jié)點
        Stu_node new_head = stack.pop();
        Stu_node cur = new_head;
        //出站
        while(!stack.isEmpty()){
            Stu_node node = stack.pop();
            //將出站的節(jié)點指向取消
            node.next=null;
            //將新的鏈表串起來
            cur.next = node;
            cur = node;
        }
        return new_head;
    }

四、完整代碼奉上

import java.util.Stack;

public class revere_node {
    public static void main(String[] args) {
        LinkedNode list= new LinkedNode();
        Stu_node node1 = new Stu_node(1,"張三");
        Stu_node node2 = new Stu_node(2,"李四");
        Stu_node node3 = new Stu_node(3,"王二");
        Stu_node node4 = new Stu_node(4,"麻子");
        Stu_node node5 = new Stu_node(5,"趙六");
        //打印添加節(jié)點之前的鏈表
        list.print();
        //尾結(jié)點添加節(jié)點
        list.add(node1);
        list.add(node2);
        list.add(node3);
        list.add(node4);
        list.add(node5);
        //打印添加加點之后的鏈表
        list.print();
        System.out.println("-------------------");
        //定義一個頭結(jié)點接收調(diào)用函數(shù)返回的頭節(jié)點
        Stu_node head = list.reverse_stack(list.head);
        //遍歷輸出每個節(jié)點
        while (head.next!=null){
            System.out.println(head);
            head=head.next;
        }

    }
}
//定義一個鏈表的操作類
class LinkedNode{
    //定義一個頭結(jié)點
    Stu_node head = new Stu_node(-1," ");
    //添加鏈表的方法
    public void add(Stu_node node){
        Stu_node temp = head;
        while(true){
            if (temp.next==null)
                break;
            temp=temp.next;
        }
        temp.next=node;
    }
    //打印鏈表
    public void print(){
        Stu_node temp = head.next;
        if (head.next==null){
            System.out.println("此鏈表為空");
        }
        while (temp!=null){
            System.out.println(temp);
            temp=temp.next;
        }
    }
    //原地反轉(zhuǎn)
    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;
    }
    //新建一個新的鏈表，頭結(jié)點插入法實現(xiàn)鏈表的反轉(zhuǎn)
    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=pnext;
        }
        return dump.next;
    }
    //利用棧實現(xiàn)反轉(zhuǎn)鏈表
    public Stu_node reverse_stack(Stu_node head){
        Stack<Stu_node> stack = new Stack<>();
        Stu_node temp = head;
        //鏈表入棧
        while(temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        //取出一個節(jié)點當(dāng)做新的鏈表的頭結(jié)點
        Stu_node new_head = stack.pop();
        Stu_node cur = new_head;
        //出站
        while(!stack.isEmpty()){
            Stu_node node = stack.pop();
            //將出站的節(jié)點指向取消
            node.next=null;
            //將新的鏈表串起來
            cur.next = node;
            cur = node;
        }
        return new_head;
    }
}
//節(jié)點類
class Stu_node{
    int num;
    String name;
    Stu_node next;
    //重寫toString方法，顯示節(jié)點數(shù)據(jù)
    @Override
    public String toString() {
        return "Stu_node{" +
                "num=" + num +
                ", name='" + name + ''' +
                '}';
    }

    public Stu_node(int num, String name) {
        this.num = num;
        this.name = name;
    }
}

總結(jié)

到此這篇關(guān)于使用 Java 如何實現(xiàn)單鏈表反轉(zhuǎn)的多種方法的文章就介紹到這了,想要了解更多相關(guān) Java 數(shù)據(jù)結(jié)構(gòu)的其他內(nèi)容請搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持！