反轉單鏈表，雙鏈表

import java.util.ArrayList; import java.util.List;public class ReverseList {public static class Node{public int value;public Node next;public Node(int data){value = data;}}public static class DoubleNode{public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data){value = data;}}// 利用雙指針，反轉單鏈表// head a - > b - > c - > d - > e - > nullpublic static Node reverseLinkedList(Node head){Node pre = null;Node next = null;while(null != head){next = head.next;head.next = pre;pre = head;head = next;}return pre;}// 反轉雙向鏈表public static DoubleNode reverseDoubleList(DoubleNode head){DoubleNode pre = null;DoubleNode next = null;while(head != null){next = head.next;head.next = pre;head.last = next;pre = head;head = next;}return pre;}public static Node testReverseLinkedList(Node head){if(null == head){return null;}ArrayList<Node> list = new ArrayList<>();while(head != null){list.add(head);head = head.next;}list.get(0).next = null;int N = list.size();for (int i = 1; i < N; i++) {list.get(i).next = list.get(i-1);}return list.get(N-1);}public static Node generateRandomLinkedList(int len, int value){int size = (int)(Math.random() * (len+1));if(size == 0){return null;}size--;Node head = new Node((int)(Math.random())*(value+1));Node pre = head;while(size != 0){Node cur = new Node((int)(Math.random())*(value+1));pre.next = cur;pre = cur;size--;}return head;}public static List<Integer> getLinkedListOriginOrder(Node head){List<Integer> ans = new ArrayList<>();while(head != null){ans.add(head.value);head = head.next;}return ans;}public static boolean checkLinkedListReverse(List<Integer> origin, Node head){for (int i = origin.size()-1; i >= 0 ; i--) {if(!origin.get(i).equals(head.value)){return false;}head = head.next;}return true;}public static void main(String[] args) {int len = 50;int value = 100;int testTime = 100000;System.out.println("test Begin!!");for (int i = 0; i < testTime; i++) {Node node1 = generateRandomLinkedList(len,value);List<Integer> list1 = getLinkedListOriginOrder(node1);node1 = reverseLinkedList(node1);if(!checkLinkedListReverse(list1,node1)){System.out.println("Oops1!");}}System.out.println("test end!!");}// 刪除鏈表中值等于num的節點public static Node removeValue(Node head, int num){while(null != head){// 來到第一個不需要刪的位置if(head.value != num){break;}head = head.next;}Node pre = head;Node cur = head;while(cur != null){if(cur.value == num){pre.next = cur.next;}else{pre = cur;}cur = cur.next;}return head;} }

隊列和棧是邏輯上的概念

數組和鏈表都能實現隊列和棧。

雙端鏈表實現隊列

public class DoubleEndsQueueToStackAndQueue {public static class Node<T>{public T value;public Node<T> last;public Node<T> next;public Node(T data){value = data;}}// 雙端隊列public static class DoubleEndsQueue<T>{public Node<T> head; // 頭指針public Node<T> tail; // 尾指針// 從頭部加public void addFromHead(T value){Node<T> cur = new Node(value);if(head == null){head = cur;tail = cur;}else{head.last = cur;cur.next = head;head = cur;}}// 從尾部加public void addFromBottom(T value){Node<T> cur = new Node(value);if(tail == null){head = cur;tail = cur;}else{tail.next = cur;cur.last = tail;tail = cur;}}// 從頭部彈出來public T popFromHead(){if(head == null){return null;}Node<T> cur = head;if(head == tail){tail = null;head = null;}else{head = head.next;cur.next = null;head.last = null;}return cur.value;}// 從尾部彈出來public T popFromTail(){if(head == null){return null;}Node<T> cur = tail;if(head == tail){tail = null;head = null;}else{tail = tail.last;tail.next = null;cur.last = null;}return cur.value;}}public static void main(String[] args) {} }

數組實現隊列

public class RingArray {public static class MyQueue{private int[] arr;private int pushi;private int polli;private int size; // 已加入到隊列中的個數private final int limit; // 隊列最多能裝多少個public MyQueue(int limit){arr = new int[limit];pushi = 0;polli = 0;size = 0;this.limit = limit;}public void push(int value){if(size == limit){throw new RuntimeException("棧滿了,不能再加了");}size++;arr[pushi] = value;pushi = nextIndex(pushi);}public int pop(int value){if(size == 0){throw new RuntimeException("棧空了,不能再拿了");}size--;int cur = arr[polli];polli = nextIndex(polli);return cur;}public boolean isEmpty(){return size == 0 ? true : false;}// 如果現在的下標值是i，返回下一個位置public int nextIndex(int i){// 如果沒到底，位置就加1。 如果位置到底，就返回0return i < limit - 1 ? i+1 : 0;}} }

實現一個特殊的棧，在實現基本功能的基礎上，再實現返回棧中最小元素的功能

pop，push，getMin操作的時間復雜度都是O(1)

設計的棧類型可以使用現成的棧結構

題目: 如何用棧結構實現隊列結構

import java.util.Stack;public class TwoStacksImplementQueue {public static class TwoStacksQueue{public Stack<Integer> stackPush;public Stack<Integer> stackPop;public TwoStacksQueue(){stackPush = new Stack<Integer>();stackPop = new Stack<Integer>();}// 從push棧往pop棧倒入數據private void pushToPop(){if(stackPop.empty()) { // 只有pop棧不為空while (!stackPush.isEmpty()) {stackPop.push(stackPush.pop());}}}public void add(int pushInt){stackPush.push(pushInt);pushToPop();}public int poll(){if(stackPush.empty() && stackPop.empty()){throw new RuntimeException("Queue is empty");}pushToPop();return stackPop.pop();}public int peek(){if(stackPush.isEmpty() && stackPop.isEmpty()){throw new RuntimeException("Queue is empty");}pushToPop();return stackPop.peek();}}public static void main(String[] args) {} }

題目: 如何用隊列結構實現棧結構

package datastructure.trainingcamp.Code03;import java.util.LinkedList; import java.util.Queue;public class TwoQueueImplementStack {public static class TwoQueueStack<T>{public Queue<T> queue;public Queue<T> help;public TwoQueueStack(){queue = new LinkedList<>();help = new LinkedList<>();}public void push(T value){queue.offer(value);}public T poll(){while(queue.size() > 1){help.offer(queue.poll());}T ans = queue.poll();Queue<T> tmp = queue;queue = help;help = tmp;return ans;}public T peek(){while(queue.size() > 1){help.offer(queue.poll());}T ans = queue.poll();help.offer(ans);Queue<T> tmp = queue;queue = help;help = tmp;return ans;}}public static void main(String[] args) {} }

任何遞歸都可以改成非遞歸

紅黑樹，avl，sb樹，跳表都能實現有序表。

總結

以上是生活随笔為你收集整理的数据结构与算法：链表，队列，栈，递归，有序表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。