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

```package com.xxx.algorithm.sort;
import java.util.Stack;
Stack<Node> stack = new Stack<Node>();
}
if(!stack.isEmpty())
while(!stack.isEmpty()){
Node node = stack.pop();
node.next = null;
cur.next = node;
cur = node;
}
}

System.out.print("list:");
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);
System.out.println("反转之后的链表：");
}
}

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`

### 3.代码实现：

```package LinkedList.Reverse;
/*
这里使用插入法进行反转链表
思路：从链表的第二个节点开始，把遍历到的节点插入到头结点的后面，直到遍历结束。
*/
public class Reverse {
public static void main(String[] args) {
//定义头结点
LNode temp=null;
//构造链表
for (int i = 1; i < 8; i++) {
temp=new LNode(); //定义一个辅助节点
temp.data=i;  //temp数据为I
temp.next=null;
cur.next=temp; //头结点的下一个节点为temp
}
System.out.println("逆序前：");
System.out.println(cur.data+" ");
}
System.out.println("逆序后：");
System.out.println(cur.data+" ");
}

}
return;
}
LNode cur=null;//定义一个当前节点
LNode next=null;//定义一个后继节点
//让当前节点指向第二个节点
//先把第一个节点设置成最后一个节点
while (cur!=null){//如果当前节点不为空
next=cur.next;//先保存当前节点的后继节点 如 2 的后面一个节点3 先保存起来
cur=next; //将当前节点指向下一个 3
}
}
}

class LNode{
LNode next;
int data;
}```

### 使用递归法

```//使用递归法
//如果链表为空或者链表只有一个元素
}else {
//反转后面的节点
//把前面遍历的节点加到后面节点逆序后链表的尾部
}
}
return;
}
//获取链表的第一个节点