7月10日学习打卡，环形链表+栈OJ

前言

大家好呀，本博客目的在于记录暑假学习打卡，后续会整理成一个专栏，主要打算在暑假学习完数据结构，因此会发一些相关的数据结构实现的博客和一些刷的题，个人学习使用，也希望大家多多支持，有不足之处也请指出，谢谢大家。

一，力扣141，判断环形链表

. - 力扣（LeetCode）

我们运用快慢指针解决这个问题，如过链表成环，那么定义一个一次走两步的快指针和一次走一步的慢指针必定相遇，因此得解

/**
 * 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) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

二，力扣142，环形链表相遇节点

. - 力扣（LeetCode）

分析：上面我们已经知道求快慢指针相遇在环形内的节点的方法，通过数学分析，可以得到当快慢指针相遇时，头节点到入口点得距离等于相遇节点到入口点距离（注意当链长但环小则不适用）下图表示为x==y，因此此时让两个指针分别在头节点和相遇节点以相同速度走，再次相遇则是入口点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        slow=head;
        if(fast==null||fast.next==null)
        return null;
        while(fast!=slow){
            slow=slow.next;
            fast=fast.next;
            
        }
        return fast;
    }

}

三，力扣20，有效括号

. - 力扣（LeetCode）

分析：这题需要用到栈的知识，思路为遇到左括号则入栈，否则，获取一个栈顶元素看是否匹配，如果栈空但遇到右括号或者走到最后栈也不为空则返回false，非常简单

class Solution {
        public boolean isValid(String s) {
            Stack<Character> st = new Stack();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == '(' || ch == '[' || ch == '{') {
                    st.push(ch);
                } else {
                    if (st.empty()) {
                        return false;
                    }
                    char ch2 =st.peek();
                    if (ch2 == '(' && ch == ')' || ch2 == '[' &&
                            ch == ']' || ch2 == '{' && ch == '}') {
                        st.pop();

                    }else{
                        return false;
                    }

                }

            }
            if(!st.empty())
            return false;
            return true;
        }
}

四，牛客JZ31，栈的压入，弹出

栈的压入、弹出序列_牛客题霸_牛客网

思路：压入数据依次入栈，如果栈顶元素于压出元素相同，则把这个元素出栈，最后如果栈为空则返回true否则返回false

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> st=new Stack<Integer>();
        int j=0;
        for(int i=0;i<pushV.length;i++){
            st.push(pushV[i]);
               while(!st.empty()&&j<popV.length
               &&st.peek()==popV[j]){
                j++;
                st.pop();
               }
              }
              if(st.empty()){
              return true;}
              return false;
        }

    }

好了，本期博客就到这里，谢谢大家。