反转单链表

  1. public Node reverseLinkedList(Node head) {
  2.     if (head == null || head.next == null) {
  3.         return head;
  4.     }
  5.     Node prev = null;
  6.     Node next = null;
  7.     while (head != null) {
  8.         next = head.next;
  9.         head.next = prev;
  10.         prev = head;
  11.         head = next;
  12.     }
  13.     return prev;
  14. }

反转双链表

  1. public DoubleNode reverseDoubleLinkedList(DoubleNode head) {
  2.     if (head == null || head.next == null) {
  3.         return head;
  4.     }
  5.     DoubleNode prev = null;
  6.     DoubleNode next = null;
  7.     while (head != null) {
  8.         next = head.next;
  9.         head.next = prev;
  10.         head.prev = next;
  11.         prev = head;
  12.         head = next;
  13.     }
  14.     return prev;
  15. }

在链表中删除指定值的所有节点

  1. public Node removeValue(Node head, int value) {
  2.     if (head == null) {
  3.         return head;
  4.     }
  5.     //考虑头节点开始就是需要删除的节点
  6.     while (head != null && head.value == value) {
  7.         head = head.next;
  8.     }
  9.     Node prev = null;
  10.     Node curr = head;
  11.     while (curr != null) {
  12.         if (curr.value == value) {
  13.             prev.next = curr.next;
  14.         } else {
  15.             prev = curr;
  16.         }
  17.         curr = curr.next;
  18.     }
  19.     return head;
  20. }

用双链表实现栈和队列

可先实现双端队列， 使用双端队列实现队列（先进先出） 使用双端队列实现栈（先进后出）

  1. //双端队列实现方法
  2. public class DoubleEndsQueue<T> {
  3.     private Node<T> head;
  4.     private Node<T> tail;
  5.     private int size;
  6.     //从头部添加
  7.     public void addFromHead(T value) {
  8.         Node<T> node = new Node<>(value);
  9.         if (head == null) {
  10.             head = node;
  11.             tail = node;
  12.         } else {
  13.             node.next = head;
  14.             head.prev = node;
  15.             head = node;
  16.         }
  17.         size++;
  18.     }
  19.     //从底部添加
  20.     public void addFromBottom(T value) {
  21.         Node<T> node = new Node<>(value);
  22.         if (tail == null) {
  23.             tail = node;
  24.             head = tail;
  25.         } else {
  26.             tail.next = node;
  27.             node.prev = tail;
  28.             tail = node;
  29.         }
  30.         size++;
  31.     }
  32.     //从头部获取
  33.     public T popFromHead() {
  34.         if (head == null) {
  35.             return null;
  36.         }
  37.         Node<T> result = head;
  38.         if (head == tail) {
  39.             head = null;
  40.             tail = null;
  41.         } else {
  42.             head = head.next;
  43.             head.prev = null;
  44.                result.next = null;
  45.         }
  46.         size--;
  47.         return result.value;
  48.     }
  49.     //从底部获取
  50.     public T popFromBottom() {
  51.         if (tail == null) {
  52.             return null;
  53.         }
  54.         Node<T> result = tail;
  55.         if (head == tail) {
  56.             head = null;
  57.             tail = null;
  58.         } else {
  59.             tail = tail.prev;
  60.             tail.next = null;
  61.             result.prev = null;
  62.         }
  63.         size--;
  64.         return result.value;
  65.     }
  67.     public int getSize() {
  68.         return size;
  69.     }
  71.     public boolean isEmpty() {
  72.         return size == 0;
  73.     }
  74. }

用环形数组实现栈和队列

技巧：在数据结构中增加一个size变量，如此可免去判断读写子指针相交问题

  1. //队列的实现
  2. public static class RingArrayQueue<T> {
  3.     private Object[] arr;
  4.     private int limit;
  5.     private int size;
  7.     private int readIdx = 0;
  8.     private int writeIdx = 0;
  10.     public RingArrayQueue(int maxSize) {
  11.         if (maxSize < 1) {
  12.             throw new InvalidParameterException("最大值需大于0，maxSize: " + maxSize);
  13.         }
  14.         this.limit = maxSize;
  15.         this.arr = new Object[maxSize];
  16.     }
  18.     public void put(T value) {
  19.         if (size == limit) {
  20.             throw new RuntimeException("容量满了");
  21.         }
  22.         arr[writeIdx++] = value;
  23.         writeIdx = writeIdx == limit ? 0 : writeIdx;
  24.         size++;
  25.     }
  27.     public T pop() {
  28.         if (size == 0) {
  29.             throw new RuntimeException("没有数据啦");
  30.         }
  31.         Object result = arr[readIdx++];
  32.         readIdx = readIdx == limit ? 0 : readIdx;
  33.         size--;
  34.         return (T) result;
  35.     }
  37.     public int getSize() {
  38.         return size;
  39.     }
  41.     public boolean isEmpty() {
  42.         return size == 0;
  43.     }
  44. }
  1. //栈的实现
  2. public class MyStack<T> {
  3.     private Object[] arr;
  4.     private int limit;
  5.     private int size;
  6.     private int writReadIdx;
  8.     public MyStack(int limit) {
  9.         if (limit < 1) {
  10.             throw new RuntimeException("limit需大于0");
  11.         }
  12.         this.limit = limit;
  13.         arr = new Object[limit];
  14.     }
  16.     public void push(T value) {
  17.         if (size == limit) {
  18.             throw new RuntimeException("容量满了");
  19.         }
  20.         arr[writReadIdx++] = value;
  21.         writReadIdx = writReadIdx == limit ? 0 : writReadIdx;
  22.         size++;
  23.     }
  25.     public T pop() {
  26.         if (size == 0) {
  27.             throw new RuntimeException("没有值了");
  28.         }
  29.         writReadIdx = writReadIdx - 1 < 0 ? limit - 1 : --writReadIdx;
  30.         size--;
  31.         return (T) arr[writReadIdx];
  32.     }
  34.     public int size() {
  35.         return size;
  36.     }
  38.     public boolean isEmpty() {
  39.         return size == 0;
  40.     }
  41. }

实现有getMin功能的栈

利用两个栈，一个栈记录数据，另一个栈同步记录当前最小的值

  1. public class GetMinStack {
  2.     private Stack<Integer> data;
  3.     private Stack<Integer> min;
  5.     public GetMinStack() {
  6.         this.data = new Stack<>();
  7.         this.min = new Stack<>();
  8.     }
  10.     public void push(int value) {
  11.         if (min.isEmpty()) {
  12.             min.push(value);
  13.         } else {
  14.             Integer preMin = min.peek();
  15.             min.push(Math.min(preMin, value));
  16.         }
  17.         data.push(value);
  18.     }
  20.     public int pop() {
  21.         min.pop();
  22.         return data.pop();
  23.     }
  25.     public int getMin() {
  26.         return min.peek();
  27.     }
  28. }

两个栈实现队列

弹出栈为空的时候才从写入栈去导入 写入栈导入弹出栈时需一次性导完

  1. public class TwoStackQueue<T> {
  2.     private Stack<T> push;
  3.     private Stack<T> pop;
  5.     public TwoStackQueue() {
  6.         this.push = new Stack<>();
  7.         this.pop = new Stack<>();
  8.     }
  10.     public void push(T value) {
  11.         push.push(value);
  12.     }
  14.     public T poll() {
  15.         pushToPop();
  16.         return pop.pop();
  17.     }
  19.     private void pushToPop() {
  20.         if (pop.isEmpty() && !push.isEmpty()) {
  21.             while (!push.isEmpty()) {
  22.                 pop.push(push.pop());
  23.             }
  24.         }
  25.     }
  27.     public T peek() {
  28.         pushToPop();
  29.         return pop.peek();
  30.     }
  32.     public boolean isEmpty() {
  33.         return pop.isEmpty() && pop.isEmpty();
  34.     }
  35. }

两个队列实现栈

弹出数据的时候，将主队列数据移动到辅助队列，再将主队列和辅助队列应用交换

  1. public static class TwoQueueStack<T> {
  2.     public Queue<T> queue;
  3.     public Queue<T> help;
  5.     public TwoQueueStack() {
  6.         queue = new LinkedList<>();
  7.         help = new LinkedList<>();
  8.     }
  10.     public void push(T value) {
  11.         queue.offer(value);
  12.     }
  14.     public T poll() {
  15.         while (queue.size() > 1) {
  16.             help.offer(queue.poll());
  17.         }
  18.         T ans = queue.poll();
  19.         Queue<T> tmp = queue;
  20.         queue = help;
  21.         help = tmp;
  22.         return ans;
  23.     }
  25.     public T peek() {
  26.         while (queue.size() > 1) {
  27.             help.offer(queue.poll());
  28.         }
  29.         T ans = queue.poll();
  30.         help.offer(ans);
  31.         Queue<T> tmp = queue;
  32.         queue = help;
  33.         help = tmp;
  34.         return ans;
  35.     }
  37.     public boolean isEmpty() {
  38.         return queue.isEmpty();
  39.     }
  41. }