数据结构面试题分析

反转单向链表

https://leetcode-cn.com/problems/reverse-linked-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;   // 下一个节点
        
        while (cur != null) {
            // 拿到原来链表head的下一个节点
            next = cur.next;
            // 把当前链表的下一个节点指向上一个节点也就是pre
            cur.next = pre;
            // 重置pre为当前链表节点
            pre = cur;
            // 重置当前节点
            cur = next;
        }
        // 返回反转后的链表 也就是pre 其实就是cur
        return pre;
    }
}

两两交换链表节点

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 初始化一个新的链表
        ListNode node = new ListNode(0);
        // 设置链表为传入链表
        node.next = head;
        // 初始化一个临时变量当前链表
        ListNode cur = node;
        // 循环当前链表 条件是两两不为空
        while (cur.next != null && cur.next.next != null) {
            // 取出相邻成对节点 
            ListNode firstNode = cur.next;
            ListNode lastNode = firstNode.next;
            // 交换节点
            // 注意第一次是前面的变成后面，所以还要继续链接后面，所以交换节点的next
            firstNode.next = lastNode.next;
            // 而第二次直接指向即可
            lastNode.next = firstNode;
            // 交换完毕 设置当前节点的指向为lastNode
            cur.next = lastNode;
            // 设置当前节点为往后两个，也就是跳过一对
            cur = cur.next.next;
        }
        return node.next;
    }
}

判断链表是否有环

image.png

https://leetcode-cn.com/problems/linked-list-cycle/

• 常见解法

  
  image.png

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 判空
        if (head == null) {
            return false;
        }
        // 快慢指针法，如果两者相遇，则存在闭环
        ListNode slow = head;
        ListNode quick = head;
        // 对慢指针进行while循环
        while (slow.next != null) {
            // 如果快指针接下来的节点和接下来两个的节点都为空 则链表结束 不存在闭环
            if (quick.next == null || quick.next.next == null) {
                return false;
            }
            // 如果两指针相同 则存在闭环
            if (quick.next.next == slow.next) {
                return true;
            }
            // 重置快慢节点 以便于下一次循环
            slow = slow.next;
            quick = quick.next.next;
        }
        return false;
    }
}

判断字符串的括号是否合法

image.png

https://leetcode-cn.com/problems/valid-parentheses/description/

• 通过压栈的方法来做

  
  image.png

class Solution {
    public boolean isValid(String s) {
        // 初始化一个栈
        Stack<Character> stack = new Stack();
        // 把字符串分成字符数组
        char[] chars = s.toCharArray();
        // 遍历字符数组
        for (char aChar : chars) {
            // 三种情况 如果栈的大小为0 则把cha插入栈底
            if (stack.size() == 0) {
                stack.push(aChar);
            }else if (isSym(stack.peek(), aChar)) {
                // 第二种情况 栈的大小不为0 但是栈底的字符和当前遍历到的字符相等 则移除该对字符
                stack.pop();
            }else {
                stack.push(aChar);
            }
        }
        // 如果stack == 0 则表示栈内的字符成对被移除完毕 则表示字符串的括号是没有问题的 一一对应的
        return stack.size() == 0;
    }
    
    // 判断括号是否相等
    private boolean isSym(char c1, char c2) {
        return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
    }
}

用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/description/

image.png

从上图可以看出，想要用栈实现队列，其实就是把栈的FILO特性改为队列的FIFO特性。
我们用两个栈倒腾一下顺序就可以实现了。

class MyQueue {
    
    // 声明两个栈
    Stack<Integer> stack1, stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        // 初始化
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        // 往栈1中添加元素
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        // pop使用的是栈2 所以先判断栈2中有木有元素，如果木有，则把栈1中的元素一个个push到栈2中
        if (!stack2.isEmpty()) {
            return stack2.pop();
        }else {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        // 将stack1全部倒腾到stack2之后，拿出stack2的第一个即可
        return stack2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        // 取出栈顶元素 类似于pop
        if (!stack2.isEmpty()) {
            return stack2.peek();
        }else {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

用队列实现栈

https://leetcode-cn.com/problems/implement-stack-using-queues/

class MyStack {
    
    // 初始化一个队列 先入先出
    private Queue<Integer> data;

    /** Initialize your data structure here. */
    public MyStack() {
        data = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        // 添加到末尾
        data.offer(x);
        // 整体逆序
        for (int i = 0; i < data.size() - 1; i++) {
            data.offer(data.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return data.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return data.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return data.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */