Java 利用栈来反转链表和排序的操作
栈是一个特殊的数据结构,特点是先进后出(First In Last Out 简称FILO),这种特殊的数据结构,可以用在对链表做反转中,或者字符串逆序,因为要把头变成尾,尾变成头,栈这种结构最合适不过了,下面来看看如何用栈来做链表的反转。
package com.xxx.algorithm.sort; import java.util.Stack; public class LinkedListReverse { public static Node reverseLinkedList(Node head){ Stack<Node> stack = new Stack<Node>(); while(head!=null){ stack.push(head); head = head.next; } if(!stack.isEmpty()) head = stack.pop(); Node cur = head; while(!stack.isEmpty()){ Node node = stack.pop(); node.next = null; cur.next = node; cur = node; } return head; } public static void display(Node head){ System.out.print("list:"); Node cur = head; while(cur!=null){ System.out.print(cur+"->"); cur = cur.next; } System.out.println(); } public static void main(String[] args) { Node a = new Node("a"); Node b = new Node("b"); Node c = new Node("c"); Node d = new Node("d"); Node e = new Node("e"); Node f = new Node("f"); Node g = new Node("g"); a.next = b; b.next = c; c.next = d; d.next = e; e.next = f; f.next = g; System.out.println("原始链表:"); display(a); Node head = reverseLinkedList(a); System.out.println("反转之后的链表:"); display(head); } } class Node{ String val; Node next; public Node(String val) { this.val = val; } @Override public String toString() { return "Node("+this.val+")"; } }
运行程序,结果如下:
原始链表:
list:Node(a)->Node(b)->Node(c)->Node(d)->Node(e)->Node(f)->Node(g)->
反转之后的链表:
list:Node(g)->Node(f)->Node(e)->Node(d)->Node(c)->Node(b)->Node(a)->
通过栈来反转链表思路很简单,这只是说了栈作为一种数据结构,其实用途很广泛。今天要介绍的另外一个栈的用途是如何通过栈来排序,利用栈来排序,需要有两个栈,一个存放原始数据,一个是辅助排序用的。
具体思路就是:将栈中的数据依次放入辅助栈中,放入辅助栈的要求是按照数据从大到小的排列(或者从小到大),先进入的是较大的数,后进入的是较小的数,如果原栈中没有数据了,说明数据已经在辅助栈中排好序了,接着我们把数据再一次性放入原栈中,如果遍历,就是一个排好序的数组了。
这里面把原栈中的数据放入辅助栈中,需要借助一个中间变量,原栈中弹出的数据放入中间变量中,而不是直接入辅助栈,如果栈顶的元素小于中间变量,那么将小于的数据再放入原栈中,再将中间变量放入辅助栈,接着再将原栈中的数据放入辅助栈,直到原栈为空。将中间变量放入辅助栈,类似插入排序,需要找到一个合适的位置,而移动出一个合适的位置,就是把辅助栈中的数据再次压入原栈中。
算法示例代码如下:
package com.xxx.algorithm.sort; import java.util.Iterator; import java.util.Stack; public class StackSortDemo { public static void sortByStack(Stack<Integer> stack){ Stack<Integer> help = new Stack<Integer>(); while(!stack.isEmpty()){ int cur = stack.pop(); while(!help.isEmpty()&&help.peek()<cur){ stack.push(help.pop()); } help.push(cur); } while(!help.isEmpty()){ stack.push(help.pop()); } } public static void display(Stack<Integer> stack){ System.out.print("stack:"); Iterator<Integer> it = stack.iterator(); while(it.hasNext()){ System.out.print(it.next()+"->"); } System.out.print("null"); System.out.println(); } public static void main(String[] args) { Stack<Integer> stack = new Stack<Integer>(); stack.push(2); stack.push(9); stack.push(5); stack.push(4); stack.push(6); stack.push(3); stack.push(8); stack.push(7); System.out.println("原始栈:"); display(stack); sortByStack(stack); System.out.println("排序之后的栈:"); display(stack); } }
运行程序,打印信息如下:
原始栈:
stack:2->9->5->4->6->3->8->7->null
排序之后的栈:
stack:2->3->4->5->6->7->8->9->null
补充:Java数据结构与算法-------链表反转(如何实现链表的逆序)
1. 问题:
链表 head -->1-->2-->3-->4-->5-->6-->7, 如何反转为head -->7-->6->5-->4-->3-->2-->1,
2.思路(使用插入法)
思路:从链表的第二个节点开始,把遍历到的节点插入到头结点的后面,直到遍历结束。
假设原链表:head -->1-->2-->3-->4-->5-->6-->7,
在遍历2的时候,链表变为head -->2-->1-->3-->4-->5-->6-->7,
3.代码实现:
package LinkedList.Reverse; /* 这里使用插入法进行反转链表 思路:从链表的第二个节点开始,把遍历到的节点插入到头结点的后面,直到遍历结束。 假设原链表:head -->1-->2-->3-->4-->5-->6-->7, 在遍历2的时候,链表变为head -->2-->1-->3-->4-->5-->6-->7, */ public class Reverse { public static void main(String[] args) { //定义头结点 LNode head=new LNode(); head.next=null; LNode temp=null; LNode cur=head; //构造链表 for (int i = 1; i < 8; i++) { temp=new LNode(); //定义一个辅助节点 temp.data=i; //temp数据为I temp.next=null; cur.next=temp; //头结点的下一个节点为temp cur=temp; //cur后移 由head移动到temp } System.out.println("逆序前:"); for (cur=head.next;cur!=null;cur=cur.next){ System.out.println(cur.data+" "); } System.out.println("逆序后:"); Reverse(head); for (cur=head.next;cur!=null;cur=cur.next){ System.out.println(cur.data+" "); } } public static void Reverse(LNode head){ if (head==null || head.next==null){//如果头结点为空,或者头结点的下一个节点为空,链表不用反转 return; } LNode cur=null;//定义一个当前节点 LNode next=null;//定义一个后继节点 //让当前节点指向第二个节点 cur=head.next.next; //先把第一个节点设置成最后一个节点 head.next.next=null; while (cur!=null){//如果当前节点不为空 next=cur.next;//先保存当前节点的后继节点 如 2 的后面一个节点3 先保存起来 cur.next=head.next;// 就是把2 的下一个节点指向1 head.next=cur;//把头结点指向2 cur=next; //将当前节点指向下一个 3 } } } class LNode{ LNode next; int data; }
使用递归法
//使用递归法 private static LNode RecursiveReverse(LNode head){ //如果链表为空或者链表只有一个元素 if (head==null || head.next==null){ return head; }else { //反转后面的节点 LNode newHead = RecursiveReverse(head.next); //把前面遍历的节点加到后面节点逆序后链表的尾部 head.next.next=head; head.next=null; return newHead; } } public static void Reverse(LNode head){ if (head==null){ return; } //获取链表的第一个节点 LNode firstNode=head.next; //对链表进行逆序 LNode newhead = RecursiveReverse(firstNode); head.next=newhead; }
以上为个人经验,希望能给大家一个参考,也希望大家多多支持猪先飞。如有错误或未考虑完全的地方,望不吝赐教。
相关文章
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 在本篇文章里小编给大家整理的是关于C#实现排序的代码以及相关知识点,需要的朋友们参考下。...2020-06-25
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- c# n个数排序实现代...2020-06-25
- 本文给大家汇总介绍了几个个人收藏的JavaScript实现冒泡排序的代码,都是非常的不错,有需要的小伙伴可以参考下...2016-06-12
- 这篇文章主要介绍了C#使用linq对数组进行筛选排序的方法,实例分析了C#实用linq扩展进行数组排序的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 冒泡排序即是对数组每次轮循出最大数或最小数放在队尾,这里我们来看一下C#实现冒泡排序算法的代码示例,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#使用自定义算法对数组进行反转操作的方法,涉及C#针对数组操作的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要为大家详细介绍了JavaScript数据结构之双向链表,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-03-07
- 排序是我们在日常开发中经常遇到的一个功能,下面这篇文章主要给大家介绍了利用JavaScript对中文(汉字)进行排序的相关资料,文中通过示例代码介绍的非常详细,对大家具有一定的参考学习价值,需要的朋友们下面跟着小编一起来看看吧。...2017-06-24
- 这篇文章主要介绍了C++ STL关联式容器自定义排序规则的2种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-04
- 但是,我们在使用中就会发现问题,这里的数组排序方法并不是按照我们想像中的数字大小来排序的,而是按照字符串测试结果改变原先的数据。这并不是我们想要的。那么如何才可以得到我们想要的按照我们思维中的数字大小来排序...2014-05-31
- 这篇文章主要介绍了C++ 字符串去重排序实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了 C语言开发之归并排序详解及实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C语言单链表实现多项式相加,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了VC++实现选择排序算法简单示例,代码简洁易懂,有助于读者对数据结构与算法的学习,需要的朋友可以参考下...2020-04-25