學(xué)習(xí)過(guò)數(shù)據(jù)結(jié)構(gòu)的小伙伴們,對(duì)單鏈表想來(lái)是并不陌生。本篇文章將為大家介紹幾種在 Java 語(yǔ)言當(dāng)中,實(shí)現(xiàn)單鏈表反轉(zhuǎn)的幾種方法,以下是具體內(nèi)容。
一、原地反轉(zhuǎn)
1、新建一個(gè)哨兵節(jié)點(diǎn)下一結(jié)點(diǎn)指向頭結(jié)點(diǎn)
2、把待反轉(zhuǎn)鏈表的下一節(jié)點(diǎn)插入到哨兵節(jié)點(diǎn)的下一節(jié)點(diǎn)
反轉(zhuǎn)之前的鏈表:1–>2–>3–>4>–>5
加入哨兵節(jié)點(diǎn):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é)點(diǎn)插法
二、新建鏈表頭結(jié)點(diǎn)插法:
新建一個(gè)頭結(jié)點(diǎn),遍歷原鏈表,把每個(gè)節(jié)點(diǎn)用頭結(jié)點(diǎn)插入到新建鏈表中。最后,新建的鏈表就是反轉(zhuǎn)后的鏈表。
public Stu_node reverse_list1 (Stu_node head){
//新建一個(gè)新的鏈表的頭結(jié)點(diǎn)
Stu_node dump = new Stu_node(-1," ");
Stu_node pcur = head;
//遍歷待反轉(zhuǎn)鏈表,頭結(jié)點(diǎn)插入到新的鏈表中
while(pcur!=null){
Stu_node pnext = pcur.next;
pcur.next = dump.next;
dump.next=pcur;
pcur=pnext;
}
//新鏈表頭結(jié)點(diǎn)不是需要返回的數(shù)據(jù),因此返回頭結(jié)點(diǎn)的下一節(jié)點(diǎn)
return dump.next;
}
三、利用棧結(jié)構(gòu)實(shí)現(xiàn)鏈表的反轉(zhuǎn)
由于棧結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)是先進(jìn)后出(后進(jìn)先出)也可以通過(guò)棧達(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;
}
//取出棧中的一個(gè)節(jié)點(diǎn)當(dāng)做新的鏈表的頭結(jié)點(diǎn)
Stu_node new_head = stack.pop();
Stu_node cur = new_head;
//出站
while(!stack.isEmpty()){
Stu_node node = stack.pop();
//將出站的節(jié)點(diǎn)指向取消
node.next=null;
//將新的鏈表串起來(lái)
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é)點(diǎn)之前的鏈表
list.print();
//尾結(jié)點(diǎn)添加節(jié)點(diǎn)
list.add(node1);
list.add(node2);
list.add(node3);
list.add(node4);
list.add(node5);
//打印添加加點(diǎn)之后的鏈表
list.print();
System.out.println("-------------------");
//定義一個(gè)頭結(jié)點(diǎn)接收調(diào)用函數(shù)返回的頭節(jié)點(diǎn)
Stu_node head = list.reverse_stack(list.head);
//遍歷輸出每個(gè)節(jié)點(diǎn)
while (head.next!=null){
System.out.println(head);
head=head.next;
}
}
}
//定義一個(gè)鏈表的操作類(lèi)
class LinkedNode{
//定義一個(gè)頭結(jié)點(diǎn)
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;
}
//新建一個(gè)新的鏈表,頭結(jié)點(diǎn)插入法實(shí)現(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;
}
//利用棧實(shí)現(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;
}
//取出一個(gè)節(jié)點(diǎn)當(dāng)做新的鏈表的頭結(jié)點(diǎn)
Stu_node new_head = stack.pop();
Stu_node cur = new_head;
//出站
while(!stack.isEmpty()){
Stu_node node = stack.pop();
//將出站的節(jié)點(diǎn)指向取消
node.next=null;
//將新的鏈表串起來(lái)
cur.next = node;
cur = node;
}
return new_head;
}
}
//節(jié)點(diǎn)類(lèi)
class Stu_node{
int num;
String name;
Stu_node next;
//重寫(xiě)toString方法,顯示節(jié)點(diǎn)數(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 如何實(shí)現(xiàn)單鏈表反轉(zhuǎn)的多種方法的文章就介紹到這了,想要了解更多相關(guān) Java 數(shù)據(jù)結(jié)構(gòu)的其他內(nèi)容請(qǐng)搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持!