2022.9.3 刷题笔记

2022-09-03

LeetCode-876 链表的中间结点

题目:给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/middle-of-the-linked-list/

思路1:先遍历一遍链表,得出链表的长度,然后就可知中间节点的位置,再进行遍历即可知中间节点。

代码实现:

public ListNode middleNode(ListNode head) {
    ListNode cur = head;
    int len = 0;
    while (cur != null){
        cur = cur.next;
        len++;
    }

    int a = len/2 + 1;

    cur = head;
    for (int i=0;i<a-1;i++){
        cur = cur.next;
    }

    return cur;
}

思路2:设置快慢指针,快指针每次移动2个,慢指针每次移动1个,当快指针遍历完后,慢指针所指向的结点就是链表的中间结点。
代码实现:

public ListNode middleNode(ListNode head) {
    ListNode slowPtr = head;
    ListNode fastPtr = head;

    while (fastPtr != null && fastPtr.next != null){
        slowPtr = slowPtr.next;
        fastPtr = fastPtr.next.next;
    }

    return slowPtr;
}

LeetCode-232 用栈实现队列

题目:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-queue-using-stacks

思路:设置一个输入栈,一个输出栈。进队直接进入输入栈。出队的时候将输入栈全部倒入输出栈,再出栈。

代码实现:

public class MyQueue {
    private static Stack<Integer> inStack;
    private static Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<Integer>();
        outStack = new Stack<Integer>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()){
            in2out();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()){
            in2out();
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.empty()&&outStack.isEmpty();
    }

    //输入栈往输出栈倒
    private void in2out(){
        while (!inStack.isEmpty()){
            outStack.push(inStack.pop());
        }
    }
}