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;

 }

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。如有错误或未考虑完全的地方，望不吝赐教。