public static ListNode merge2Lists(ListNode x, ListNode y) {//AC
    	if (x == null) return y;
    	else if (y == null) return x;
    	else {//normal situations
    		ListNode dummy = new ListNode(0);
    		ListNode tail = dummy;
    		while (x != null && y != null) {
    			if (x.val < y.val) {
    				tail.next = x;
    				x = x.next;
    				tail = tail.next;
    				tail.next = null;
    			}
    			else {
    				tail.next = y;
    				y = y.next;
    				tail = tail.next;
    				tail.next = null;
    			}
    		}
    		//one of the lists is finished
    		if (x != null) {
    			tail.next = x;
    			return dummy.next;
    		}
    		else {
    			tail.next = y;
    			return dummy.next;
    		}
    	}
    }