class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1=nums1.length, l2=nums2.length, l=l1+l2;
        int num[] = new int[l], i=0, j=0;
        for(; i<l1 || j<l2; ){
            if(i<l1 && j<l2){
                if(nums1[i]>nums2[j])
                    num[i+j]=nums2[j++];
                else
                    num[i+j]=nums1[i++];
            }else if(i<l1)
                num[i+j]=nums1[i++];
            else
                num[i+j]=nums2[j++];
        }
        return l%2==0 ? (num[l/2-1]+num[l/2])/2.0 : (double)num[l/2];
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        ListNode res=lists[0];        
        for(int i=1; i<lists.length; i++)
            res=merge(res, lists[i]);
        return res;
    }
    public ListNode merge(ListNode res, ListNode list){
        ListNode l1=new ListNode(0);
        ListNode head=l1;
        while(res!=null && list!=null){
            if(res.val<list.val){
                l1.next=res;
                res=res.next;
            }else{
                l1.next=list;
                list=list.next;
            }
            l1=l1.next;
        }
        while(res!=null){
            l1.next=res;
            res=res.next;
            l1=l1.next;
        }
        while(list!=null){
            l1.next=list;
            list=list.next;
            l1=l1.next;
        }
        return head.next;
    }
}

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);}
    public boolean solve(char[][] board){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]=='.'){
                    for(char k='1'; k<='9'; k++){
                        if(isValidSudoku(board, i, j, k)){
                            board[i][j]=k;
                            if(solve(board))return true;
                            else board[i][j]='.';
                        }
                    }return false;}}}return true;}
    public boolean isValidSudoku(char[][] board, int r, int c, char k) {
        for(int i=0; i<9; i++){ 
            if(board[r][i] != '.' && board[r][i] == k) return false;
            if(board[i][c] != '.' && board[i][c] == k) return false;
            if(board[3*(r/3)+i/3][3*(c/3)+i%3] != '.' 
               && board[3*(r/3)+i/3][3*(c/3)+i%3] == k) return false;
        }return true;}}