Java 利用栈来反转链表和排序的操作
栈是一个特殊的数据结构，特点是先进后出(FirstInLastOut简称FILO)，这种特殊的数据结构，可以用在对链表做反转中，或者字符串逆序，因为要把头变成尾，尾变成头，栈这种结构最合适不过了，下面来看看如何用栈来做链表的反转。
packagecom.xxx.algorithm.sort;
importjava.util.Stack;
publicclassLinkedListReverse{
publicstaticNodereverseLinkedList(Nodehead){
Stackstack=newStack();
while(head!=null){
stack.push(head);
head=head.next;
}
if(!stack.isEmpty())
head=stack.pop();
Nodecur=head;
while(!stack.isEmpty()){
Nodenode=stack.pop();
node.next=null;
cur.next=node;
cur=node;
}
returnhead;
}
publicstaticvoiddisplay(Nodehead){
System.out.print("list:");
Nodecur=head;
while(cur!=null){
System.out.print(cur+"->");
cur=cur.next;
}
System.out.println();
}
publicstaticvoidmain(String[]args){
Nodea=newNode("a");
Nodeb=newNode("b");
Nodec=newNode("c");
Noded=newNode("d");
Nodee=newNode("e");
Nodef=newNode("f");
Nodeg=newNode("g");
a.next=b;
b.next=c;
c.next=d;
d.next=e;
e.next=f;
f.next=g;
System.out.println("原始链表：");
display(a);
Nodehead=reverseLinkedList(a);
System.out.println("反转之后的链表：");
display(head);
}
}
classNode{
Stringval;
Nodenext;
publicNode(Stringval){
this.val=val;
}
@Override
publicStringtoString(){
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)->
通过栈来反转链表思路很简单，这只是说了栈作为一种数据结构，其实用途很广泛。今天要介绍的另外一个栈的用途是如何通过栈来排序，利用栈来排序，需要有两个栈，一个存放原始数据，一个是辅助排序用的。
具体思路就是：将栈中的数据依次放入辅助栈中，放入辅助栈的要求是按照数据从大到小的排列（或者从小到大），先进入的是较大的数，后进入的是较小的数，如果原栈中没有数据了，说明数据已经在辅助栈中排好序了，接着我们把数据再一次性放入原栈中，如果遍历，就是一个排好序的数组了。
这里面把原栈中的数据放入辅助栈中，需要借助一个中间变量，原栈中弹出的数据放入中间变量中，而不是直接入辅助栈，如果栈顶的元素小于中间变量，那么将小于的数据再放入原栈中，再将中间变量放入辅助栈，接着再将原栈中的数据放入辅助栈，直到原栈为空。将中间变量放入辅助栈，类似插入排序，需要找到一个合适的位置，而移动出一个合适的位置，就是把辅助栈中的数据再次压入原栈中。
算法示例代码如下：
packagecom.xxx.algorithm.sort;
importjava.util.Iterator;
importjava.util.Stack;
publicclassStackSortDemo{
publicstaticvoidsortByStack(Stackstack){
Stackhelp=newStack();
while(!stack.isEmpty()){
intcur=stack.pop();
while(!help.isEmpty()&&help.peek()stack){
System.out.print("stack:");
Iteratorit=stack.iterator();
while(it.hasNext()){
System.out.print(it.next()+"->");
}
System.out.print("null");
System.out.println();
}
publicstaticvoidmain(String[]args){
Stackstack=newStack();
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.代码实现：
packageLinkedList.Reverse;
/*
这里使用插入法进行反转链表
思路：从链表的第二个节点开始，把遍历到的节点插入到头结点的后面，直到遍历结束。
假设原链表：head-->1-->2-->3-->4-->5-->6-->7,
在遍历2的时候，链表变为head-->2-->1-->3-->4-->5-->6-->7,
*/
publicclassReverse{
publicstaticvoidmain(String[]args){
//定义头结点
LNodehead=newLNode();
head.next=null;
LNodetemp=null;
LNodecur=head;
//构造链表
for(inti=1;i<8;i++){
temp=newLNode();//定义一个辅助节点
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+"");
}
}
publicstaticvoidReverse(LNodehead){
if(head==null||head.next==null){//如果头结点为空，或者头结点的下一个节点为空，链表不用反转
return;
}
LNodecur=null;//定义一个当前节点
LNodenext=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
}
}
}
classLNode{
LNodenext;
intdata;
}
使用递归法
//使用递归法
privatestaticLNodeRecursiveReverse(LNodehead){
//如果链表为空或者链表只有一个元素
if(head==null||head.next==null){
returnhead;
}else{
//反转后面的节点
LNodenewHead=RecursiveReverse(head.next);
//把前面遍历的节点加到后面节点逆序后链表的尾部
head.next.next=head;
head.next=null;
returnnewHead;
}
}
publicstaticvoidReverse(LNodehead){
if(head==null){
return;
}
//获取链表的第一个节点
LNodefirstNode=head.next;
//对链表进行逆序
LNodenewhead=RecursiveReverse(firstNode);
head.next=newhead;
}
以上为个人经验，希望能给大家一个参考，也希望大家多多支持毛票票。如有错误或未考虑完全的地方，望不吝赐教。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。