Offer to review (Simple 3)

Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.

Example 1:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

0 <= List length <= 1000

21) leetcode-cn.com/problems/me…

51,372 passes and 69,326 submissions

java

/** * 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) {
        ListNode res = new ListNode(0);
        ListNode p = res;
        while(l1! =null && l2! =null){if(l1.val<=l2.val){
                res.next = l1;
                l1 = l1.next;
                
            }
            else{
                res.next = l2;
                l2 = l2.next;
               
            }
            res = res.next;
        }
        if(l1==null && l2! =null){ res.next = l2; }if(l1! =null && l2==null){ res.next = l1; }returnp.next; }}Copy the code

python

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p = ListNode(0)
        res = p
        while l1 and l2:
            if l1.val <= l2.val:
                res.next = l1
                l1 = l1.next
            else:
                res.next = l2
                l2 = l2.next
            res = res.next
        if not l1:
            res.next = l2
        else:
            res.next = l1
        return p.next
Copy the code

Implement a function to determine whether a binary tree is symmetric. A binary tree is symmetric if it is the same as its mirror image.

java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }else{
            returnisS(root.left,root.right); }}boolean isS(TreeNode L,TreeNode R){
            if(L==null && R==null){
                return true;
            }
            if(L==null || R==null || L.val! =R.val){return false;
            }
            returnisS(L.left,R.right) && isS(L.right,R.left); }}Copy the code

python

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
    
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def isS(L,R):
            if not L and not R:
                return True
            if not L or not R or L.val!=R.val:
                return False
            return isS(L.left,R.right) and isS(L.right,R.left)

        if not root :
            return True
        return isS(root.left,root.right)
    
Copy the code

Define the data structure of the stack. Please implement a min function in this type that can get the smallest element of the stack. In this stack, the time complexity of calling min, push and pop is O(1).

Example:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); –> return -3.minstack.pop (); minStack.top(); –> return 0. Minstack.min (); — — > to return to 2.

Tip:

The total number of calls for each function does not exceed 20000 times

Answer:

Define two queues or stacks. When pushing into A, determine whether it can push into B as well. When pushing out of the queue, if A enters and exits the same as the last one of B, then B also exits

java

class MinStack {
    Stack<Integer> A, B;
    /** initialize your data structure here. */
    public MinStack(a) {
        A = new Stack<>();
        B = new Stack<>();
    }
    
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x){ B.add(x); }}public void pop(a) {
        if(A.pop().equals(B.peek())){ B.pop(); }}public int top(a) {
        return A.peek();
    }
    
    public int min(a) {
        returnB.peek(); }}/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.min(); * /
Copy the code

python

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.A = []
        self.B = []


    def push(self, x):
        """ :type x: int :rtype: None """
        self.A.append(x)
        if not  self.B or self.B[- 1]>=x:
            self.B.append(x)


    def pop(self):
        """ :rtype: None """
        if self.A.pop() == self.B[- 1]:
            self.B.pop()


    def top(self):
        """ :rtype: int """
        return self.A[- 1]

    def min(self):
        """ :rtype: int """
        return self.B[- 1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()
Copy the code