Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

How to use Java to realize the inversion of single linked list

2025-01-26 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >

Share

Shulou(Shulou.com)06/01 Report--

本篇内容主要讲解"怎么使用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 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 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实现单链表的反转"有了更深的了解,不妨来实际操作一番吧!这里是网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.

Views: 296

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report