Java 利用栈来反转链表和排序的操作

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 stack = new Stack();

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 stack){

Stack help = new Stack();

while(!stack.isEmpty()){

int cur = stack.pop();

while(!help.isEmpty()&&help.peek()

stack.push(help.pop());

}

help.push(cur);

}

while(!help.isEmpty()){

stack.push(help.pop());

}

}

public static void display(Stack stack){

System.out.print("stack:");

Iterator 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 stack = new Stack();

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;

/http:///对链表进行逆序

LNode newhead = RecursiveReverse(firstNode);

head.next=newhead;

}

stack.push(help.pop());

}

help.push(cur);

}

while(!help.isEmpty()){

stack.push(help.pop());

}

}

public static void display(Stack stack){

System.out.print("stack:");

Iterator 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 stack = new Stack();

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;

/http:///对链表进行逆序

LNode newhead = RecursiveReverse(firstNode);

head.next=newhead;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。