2ms Easy to understand Java Solution with explanation and O(n) complexity


  • 0
    G

    Main rationale here is to have a backup List which we we will keep on appending as we find the next higher number

    We put a boundary conditions first like if list 1 is empty then return list 2 and vice versa
    If both are null then return null

    Then we start while loop in which terminating condition is that both list should be iterated

    We start from head of list and whichever list has small element that we put in backup list and increment pointer for that last because we are done with that element

    If both have same element then add that element twice (my iniital test case failed because I was not handling this)
    In the end we get merged sorted list

    We return back.up.next because we initialized backup with some random value (0 on this case)
    ...
    /**

    • Definition for singly-linked list.

    • public class ListNode {

    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */
      public class Solution {
      public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

       ListNode ans = new ListNode(0);
       ListNode backup = ans;
       
       if(l1==null && l2==null) {
       	return null;
       }
       
       if(l1==null && l2!=null) {
       	return l2;
       }
      
       if(l2==null && l1!=null) {
       	return l1;
       }        
       while(l1!=null || l2!=null) {
       	//check which one is smaller
       	if(l1==null && l2!=null) {
       		ans.next = new ListNode(l2.val);
       		ans = ans.next;
       		l2 = l2.next;
       		continue;
       	}
      
       	if(l2==null && l1!=null) {
       		ans.next = new ListNode(l1.val);
       		ans = ans.next;
       		l1 = l1.next;
       		continue;
       	}        	
       	
       	if(l1.val<l2.val) {
       		ans.next = new ListNode(l1.val);
       		ans = ans.next;
       		l1 = l1.next;
       	}
       	else if(l1.val==l2.val) {
       		ans.next = new ListNode(l1.val);
       		ans = ans.next;
       		ans.next = new ListNode(l2.val);
       		ans = ans.next;
       		l1 = l1.next;
       		l2 = l2.next;
       	}
       	else {
       		ans.next = new ListNode(l2.val);
       		ans = ans.next;
       		l2 = l2.next;      		
       	}
       }
       return backup.next;
      

      }
      }
      ...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.