Java uses stacks to reverse linked lists and sort operations

Stack is a special data structure, which is characterized by first in and then out (First In Last Out for short FILO). This special data structure can be used to reverse the linked list, or the string is reversed, because it is necessary to turn the head into the tail and the tail into the head. This structure of stack is the most suitable. Let's take a look at how to reverse the linked list with stack.

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(" Original linked list: ");
 display(a);
 Node head = reverseLinkedList(a);
 System.out.println(" Inverted linked list: ");
 display(head);
 }
}
 
class Node{
 String val;
 Node next;
 public Node(String val) {
 this.val = val;
 }
 @Override
 public String toString() {
 return "Node("+this.val+")";
 }
}

Run the program and the result is as follows:

Original linked list:

list:Node(a)->Node(b)->Node(c)->Node(d)->Node(e)->Node(f)->Node(g)->

Inverted linked list:

list:Node(g)->Node(f)->Node(e)->Node(d)->Node(c)->Node(b)->Node(a)->

The idea of reversing linked list through stack is very simple, which only says that stack is a data structure, but it is widely used. The purpose of another stack to be introduced today is how to sort by stack. To sort by stack, two stacks are needed, one for storing original data and one for auxiliary sorting.

The specific idea is: Put the data in the stack into the auxiliary stack in turn, The requirement of putting into the auxiliary stack is to arrange the data from big to small (or from small to large). First, a larger number is entered, and then a smaller number is entered. If there is no data in the original stack, it means that the data has been ordered in the auxiliary stack. Then we put the data into the original stack once again. If we traverse, it is an ordered array.

In this case, the data in the original stack is put into the auxiliary stack, With the help of an intermediate variable, the data popped up from the original stack is put into the intermediate variable instead of directly into the auxiliary stack. If the element at the top of the stack is smaller than the intermediate variable, then the smaller data is put into the original stack, then the intermediate variable is put into the auxiliary stack, and then the data in the original stack is put into the auxiliary stack until the original stack is empty. Putting intermediate variables into the auxiliary stack is similar to insertion sorting, which requires finding a suitable position, and moving out of a suitable position means pressing the data in the auxiliary stack into the original stack again.

The example code of the algorithm is as follows:

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(" Raw stack: ");
 display(stack);
 sortByStack(stack);
 System.out.println(" Stack after sorting: ");
 display(stack); 
 }
}

Run the program and print the following information:

Raw stack:

stack:2->9->5->4->6->3->8->7->null

Stack after sorting:

stack:2->3->4->5->6->7->8->9->null

Supplement: Java data structure and algorithm------linked list reversal (how to realize the reverse order of linked list)

1. Issues:

Linked list head-- > 1-- > 2-- > 3-- > 4-- > 5-- > 6-- > 7. How to reverse it to head- > 7-- > 6- > 5-- > 4-- > 3-- > 2-- > 1,

2. Thinking (using insertion method)

Idea: Starting from the second node of the linked list, insert the traversed node into the back of the head node until the end of traversal.

Suppose the original linked list: head-- > 1-- > 2-- > 3-- > 4-- > 5-- > 6-- > 7,

When traversing 2, the linked list becomes head-- > 2-- > 1-- > 3-- > 4-- > 5-- > 6-- > 7,

3. Code implementation:

package LinkedList.Reverse;
/*
  Insertion is used here to reverse the linked list 
  Thoughts: From the first part of the linked list 2 Nodes, insert the traversed node after the head node until the end of the traversal. 
  Suppose the original linked list: head -->1-->2-->3-->4-->5-->6-->7,
  In traversal 2 The linked list becomes head -->2-->1-->3-->4-->5-->6-->7,
 */
public class Reverse {
 public static void main(String[] args) {
  // Define header node 
  LNode head=new LNode();
  head.next=null;
  LNode temp=null;
  LNode cur=head;
  // Construct linked list 
  for (int i = 1; i < 8; i++) {
   temp=new LNode(); // Definition 1 Secondary nodes 
   temp.data=i;  //temp The data is I
   temp.next=null;
   cur.next=temp; // Under the head node 1 Nodes are temp
   cur=temp;  //cur Backward movement   By head Move to temp
  }
  System.out.println(" Before reverse order: ");
  for (cur=head.next;cur!=null;cur=cur.next){
   System.out.println(cur.data+" ");
  }
  System.out.println(" After reverse order: ");
  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){// If the header node is empty, or the lower of the header node 1 Nodes are empty, so the linked list does not need to be reversed 
   return;
  }
  LNode cur=null;// Definition 1 Current nodes 
  LNode next=null;// Definition 1 Successor nodes 
  // Makes the current node point to the 2 Nodes 
  cur=head.next.next;
  // Put the first 1 Nodes set to last 1 Nodes 
  head.next.next=null;
  while (cur!=null){// If the current node is not empty 
   next=cur.next;// Save the successor node of the current node first   Such as  2  The back of 1 Nodes 3  Save it first 
   cur.next=head.next;//  Is to put 2  Under the 1 Nodes point to 1
   head.next=cur;// Point the head node to 2
   cur=next; // Points the current node down 1 A  3
  }
 }
}
 
class LNode{
 LNode next;
 int data;
}

Use recursion

// Use recursion 
 private static LNode RecursiveReverse(LNode head){
  // If the linked list is empty or the linked list only 1 Elements 
  if (head==null || head.next==null){
   return head;
  }else {
   // Reverse the following node 
   LNode newHead = RecursiveReverse(head.next);
   // Add the node traversed before to the end of the linked list after the reverse order of the following nodes 
   head.next.next=head;
   head.next=null;
   return newHead;
  }
 }
 public static void Reverse(LNode head){
  if (head==null){
   return;
  }
  // Gets the number of the linked list 1 Nodes 
  LNode firstNode=head.next;
  // Reverse the linked list 
  LNode newhead = RecursiveReverse(firstNode);
  head.next=newhead;
 
 }