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; }二、新建鏈表頭結點插法

二、新建鏈表頭結點插法：

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

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; }三、利用棧結構實現鏈表的反轉

由于棧結構存儲數據是先進后出（后進先出）也可以通過棧達到反轉鏈表的目的。

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;}//取出棧中的一個節點當做新的鏈表的頭結點Stu_node new_head = stack.pop();Stu_node cur = new_head;//出站while(!stack.isEmpty()){ Stu_node node = stack.pop(); //將出站的節點指向取消 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,'趙六');//打印添加節點之前的鏈表list.print();//尾結點添加節點list.add(node1);list.add(node2);list.add(node3);list.add(node4);list.add(node5);//打印添加加點之后的鏈表list.print();System.out.println('-------------------');//定義一個頭結點接收調用函數返回的頭節點Stu_node head = list.reverse_stack(list.head);//遍歷輸出每個節點while (head.next!=null){ System.out.println(head); head=head.next;} }}//定義一個鏈表的操作類class LinkedNode{ //定義一個頭結點 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;} } //原地反轉 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; } //新建一個新的鏈表，頭結點插入法實現鏈表的反轉 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; } //利用棧實現反轉鏈表 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;}//取出一個節點當做新的鏈表的頭結點Stu_node new_head = stack.pop();Stu_node cur = new_head;//出站while(!stack.isEmpty()){ Stu_node node = stack.pop(); //將出站的節點指向取消 node.next=null; //將新的鏈表串起來 cur.next = node; cur = node;}return new_head; }}//節點類class Stu_node{ int num; String name; Stu_node next; //重寫toString方法，顯示節點數據 @Override public String toString() {return 'Stu_node{' +'num=' + num +', name=’' + name + ’’’ +’}’; } public Stu_node(int num, String name) {this.num = num;this.name = name; }}總結

到此這篇關于Java實現單鏈表反轉的多種方法的文章就介紹到這了,更多相關Java單鏈表反轉方法內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！