3.2 leet20|21#括号配对#链表

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

class Solution {
    public boolean isValid(String s) {
        String sta=new String("");

        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='[')
                sta+=s.charAt(i);
            if(s.charAt(i)==')')
            {
                if(sta.charAt(sta.length()-1)=='(')
                    sta=sta.substring(0,sta.length()-1);
                else
                    return false;
            }
            if(s.charAt(i)=='}')
            {
                if(sta.charAt(sta.length()-1)=='{')
                    sta=sta.substring(0,sta.length()-1);
                else
                    return false;
            }
            if(s.charAt(i)==']')
            {
                if(sta.charAt(sta.length()-1)=='[')
                    sta=sta.substring(0,sta.length()-1);
                else
                    return false;
            }            
        }
        if(sta=="")
            return true;
        else
            return false;
    }
}

思路就是用栈，但不会写栈，就写了个string。
算法：
循环判断：

1. 如果是({[，就加入字符串sta中
2. 如果是})]，就在字符串sta中找有没有匹配的左括号，：
   1 sta为空，false
   2 sta中有，则删除
   3 sta中没有，false
3. 字符串为空，true；否则false。

class Solution {
    public boolean isValid(String s) {
        String sta=new String("");
    
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='[')
                sta+=s.charAt(i);
            if(s.charAt(i)==')')
            {
                if(sta.length()<1)
                    return false;
                else if(sta.charAt(sta.length()-1)=='(')
                    sta=sta.substring(0,sta.length()-1);
                else
                    return false;
            }
            if(s.charAt(i)=='}')
            {
                if(sta.length()<1)
                    return false;
                else if(sta.charAt(sta.length()-1)=='{')
                    sta=sta.substring(0,sta.length()-1);
                else
                    return false;
            }
            if(s.charAt(i)==']')
            {
                if(sta.length()<1)
                    return false;
                else if(sta.charAt(sta.length()-1)=='[')
                    sta=sta.substring(0,sta.length()-1);
                else
                    return false;
            }
        }
        if(sta.length()==0)     
            return true;                    
        else        
            return false;   
    }
}

1. 一开始在步骤2没有考虑到sta为空，会溢出。然后就在判断sta有无左括号前加一个是否为空的判断。
2. 在最后判断字符串为空时，一开始用的是 但是判断的结果不对，是空的也会判成不是。？？
   https://leetcode.com/problems/merge-two-sorted-lists/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        else if(l2==null)
            return l1;
        else if(l1.val<=l2.val)
        {
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
        else{        
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

怎么写链表：其实很简单
class node {node next;}
node now = new node();
now.next = new node();
new就完事