【数算-3】链表结构（实现栈和队列）

爱被打了一巴掌 2022-10-08 11:28 196阅读 0赞

> 面试题目的最优解，确定最优解  
> 有区分度的题目 》 考的万无一失的题目；高频题目  
> 在痛苦就听下去，  
> 【面试】锻炼一种能力，絮絮叨叨的把想法想出来，完成思路的碰撞。从人性出发，絮絮叨叨弄出来，面试官：“我帮你一下”，絮絮叨叨又不要招人烦。牛逼啊，太牛逼了。

## 链表结构： ##

给定一个 Node 结构：

public static class Node {
        
        public int value;
        public Node next;
    
        public Node(int data) {
        
            this.value = data;
        }
    }

## 1) 单链表和双链表如何反转 ##

### 1.1 单向链表 ###

这是一个单链表结构， 假设初始时，a --> b --> c --> null ：

那么如何实现指针的反转，最终 c --> b --> a --> null ?

**代码实现：**

public static Node reverseLinkedList(Node head) {
        
        Node pre = null;
        Node next = null;
        while (head != null) {
        
            // 保存好下一个结点要用的head 的指针，不然就不知道一会应该操作谁了。
            next = head.next;
            // 改变当前 head 的指针，使其指向 pre，指回去
            head.next = pre;
            // 把pre存好给下一个用，不然下一个就不知道指向哪里了。
            pre = head;
            // 把 next 下一次循环的 head
            head = next;
        }
        // 返回pre 元素，就是返回头节点。
        return pre;
    }

![pic1][]

### 1.2 双向链表 ###

public class LinkedListTest2 {
        
    
        public static Node[] nodes = new Node[3];
    
        static {
        
            Node a = new Node(1);
            Node b = new Node(2);
            Node c = new Node(3);
            a.prev = null;
            a.next = b;
            b.prev = a;
            b.next = c;
            c.prev = b;
            c.next = null;
            nodes[0] = a;
            nodes[1] = b;
            nodes[2] = c;
        }
    
        public static void main(String[] args) {
        
            Node head = nodes[0];
            printNodes(head);
            Node newHead = reverseLinkedList(head);
            System.out.println("\n反转后：");
            printNodes(newHead);
        }
    
        public static void printNodes(Node head) {
        
            while (head != null) {
        
                System.out.println(head.prev + " <-- " + head.value + " --> " + head.next);
                head = head.next;
            }
        }
    
        public static class Node {
        
            public Node prev;
            public int value;
            public Node next;
    
            public Node(int value) {
        
                this.value = value;
            }
            public String toString() {
        
                return Integer.valueOf(value).toString();
            }
        }
    
        /**
         * prev --> head --> next
         */
        public static Node reverseLinkedList(Node head) {
        
            Node prev = null;
            Node next = null;
            while (head != null) {
        
                next = head.next;
                prev = head.prev;
                head.prev = next;
                head.next = prev;
                prev = head;
                head = next;
            }
            return prev;
        }
    }

![pic1][pic1 1]

## 2) 把给定值都删除 ##

/**
         * 2 -> 2-> 3-> 2-> 3-> 4
         * 若：删除 num = 3，得到：
         * 2 -> 2-> 2-> 4，return head = 2
         * 若：删除 num = 2 得到：
         * 3-> 3-> 4 ，return head= 3
         * @param head
         * @param val
         * @return
         */
        public static ListNode removeValue(ListNode head, int val) {
        
            // head 来到第一个不需要删除的位置
            while(head != null) {
        
                if (head.val != val) {
        
                    break;
                }
                head = head.next;
            }
            // 1、head == null 表示所有 node 都是 num，return null
            // 2、head != null
            ListNode prev = head;
            ListNode curr = head;
            while (curr != null) {
        
                if (curr.val == val)
                    prev.next = curr.next;
                else
                    prev = curr;
                curr = curr.next;
            }
            return head;
        }

### 1.3 java内存泄漏： ###

Java使用的是可达性算法，对于不可达对象会随时释放（自动释放内存

## 2. 栈和队列的实际实现： ##

栈：数据先进后出，犹如弹匣

队列：数据先进先出，好似排队

### 2.1 **双向链表** （对栈和队列）的实现： ###

保留**头进和头出**

保留**头进和尾出**

**双向链表**

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<T>(value);
    			if (head == null) {
        
    				head = cur;
    				tail = cur;
    			} else {
        
    				cur.next = head;
    				head.last = cur;
    				head = cur;
    			}
    		}
    
    		public void addFromBottom(T value) {
        
    			Node<T> cur = new Node<T>(value);
    			if (head == null) {
        
    				head = cur;
    				tail = cur;
    			} else {
        
    				cur.last = tail;
    				tail.next = cur;
    				tail = cur;
    			}
    		}
    
    		public T popFromHead() {
        
    			if (head == null) {
        
    				return null;
    			}
    			Node<T> cur = head;
    			if (head == tail) {
        
    				head = null;
    				tail = null;
    			} else {
        
    				head = head.next;
    				cur.next = null;
    				head.last = null;
    			}
    			return cur.value;
    		}
    
    		public T popFromBottom() {
        
    			if (head == null) {
        
    				return null;
    			}
    			Node<T> cur = tail;
    			if (head == tail) {
        
    				head = null;
    				tail = null;
    			} else {
        
    				tail = tail.last;
    				tail.next = null;
    				cur.last = null;
    			}
    			return cur.value;
    		}
    
    		public boolean isEmpty() {
        
    			return head == null;
    		}
    
    	}

**栈**

public static class MyStack {
          
    	
    	private DoubleEndsQueue<
    	public MyStack() {
        
    		queue = new DoubleEndsQueue();
    	}
    
    	public void push(T value) {
        
    		queue.addFromHead(value);
    	}
    
    	public T pop() {
        
    		return queue.popFromHead();
    	}
    
    	public boolean isEmpty() {
        
    		return queue.isEmpty();
    	}
    
    }

**队列**

public static class MyQueue {
        
    		private DoubleEndsQueue queue;
    
        public MyQueue() {
        
    			queue = new DoubleEndsQueue();
    		}
    
    		public void push(T value) {
        
    			queue.addFromHead(value);
    		}
    
    		public T poll() {
        
    			return queue.popFromBottom();
    		}
    
    		public boolean isEmpty() {
        
    			return queue.isEmpty();
    		}
    
    	}

### 2.2 数组实现 ###

面试中是动态实现的

语言的api的有限的，手动改写是不确定的。

两个栈拼队列来搞、两个队列拼栈来搞。

[pic1]: /images/20221005/6899df2a0643402b8f3f85020cc5286e.png
[pic1 1]: /images/20221005/763db52ad9104fb1b21c8466c2cdb996.png