MergeTwoSortedList.java

Codeformergetwosortedlistandmakeasinglesortedlist


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

classSolution {
publicListNodemergeTwoLists(ListNodelist1, ListNodelist2) {

// The case where both lists are empty
if(list1 == null && list2 == null){
returnnull;
// The 2 cases that describe one of the other is empty
 }elseif(list1 == null && list2 != null){
returnlist2;
 } elseif (list1 != null && list2 == null) {
returnlist1;
// The case that describes the beginning of the sorting
// ie, list1's first value is smaller or equal to list2
 }elseif(list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
returnlist1; 
 }else {
list2.next = mergeTwoLists(list1, list2.next);
returnlist2;
 }
 }
}