携程笔试思路

static ListNode partition(ListNode head,int m) {
        //思路：用小链表连接大链表，遍历一遍即可
        ListNode small = new ListNode(-1020);
        ListNode smallStart = small;
        ListNode big = new ListNode(-1020);
        ListNode bigStart = big;
        while (head != null) {
            if(head.val <= m) {
                small.next = head;
                small = small.next;
            } else {
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
    //把大链表的尾部置为null
        big.next = null;
    //链接小链表和大链表
        small.next = bigStart.next;

        return smallStart.next;
    }

static String resolve(String expr) {
        //先检查左右括号个数
        int lC = 0 ;
        int rC = 0 ;
        Stack<Character> stack = new Stack();
        char[] chars = expr.toCharArray();
        for (int i = 0;i < chars.length;i++) {
            if (chars[i] == '(') lC++;
            else if(chars[i] == ')')rC++;
        }
        if(lC != rC) return "";
        //利用栈的特性来翻转，如果没遇到）就一直装到栈中，遇到）就一直pop直到把第一个（pop出来，这期间pop出来的字符装到tmp尾部，
        //再把tmp字符串按顺序装回栈里即可
        String res = "";
        for (int i = 0; i < chars.length; i++) {
            String tmp = "";
            if (chars[i] != ')') {
                stack.add(chars[i]);
            } else {
                if (stack.empty()) return "";
                while (stack.peek() != '(') {
                    tmp += stack.pop();
                    if (stack.empty()) return "";
                }
                stack.pop();
                for (int j = 0;j < tmp.length(); j++) {
                    stack.push(tmp.charAt(j));
                }
                if (i == chars.length-1) {
                    res = tmp;
                }
            }
        }
        return res;
    }