ListNode merge(ListNode list1, ListNode list2) {
		ListNode cur = new ListNode(0);
		ListNode hd = cur;

		while (list1 != null && list2 != null) {
			if (list1.val < list2.val) {
				cur.next = list1;
				cur = cur.next;
				list1 = list1.next;
			} else {
				cur.next = list2;
				cur = cur.next;
				list2 = list2.next;
			}
		}

		if (list1 != null)
			cur.next = list1;
		if (list2 != null)
			cur.next = list2;

		return hd.next;
	}