Iterative Solution


  • 0
    N

    \
    /**

    • 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)
      {
      if(l1 == null)
      return l2;
      if(l2 == null)
      return l1;

       ListNode headToReturn;
       if(l1.val < l2.val)
       {
           headToReturn = l1;
           l1 = l1.next;
       }
       else
       {
           headToReturn = l2;
           l2 = l2.next;
       }
       
       ListNode runner = headToReturn;
       while(l1 != null && l2 != null)
       {
           if(l1.val < l2.val)
           {
               runner.next = l1;
               l1 = l1.next;
           }
           else
           {
               runner.next = l2;
               l2 = l2.next;
           }
           runner = runner.next;
       }
       
       if(l1 != null)
           runner.next = l1;
       if(l2 != null)
           runner.next = l2;
       
       return headToReturn;
      

      }
      }
      \\


  • 0
    G

    You can initialize headToReturn with a dummy value. When return the result, just return headToReturn.next.
    In this case, you don't have to worry about l1/l2 head value anymore, just do the while loop will take care of that.

    public class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2){
            if(l1 == null) return l2;
            if(l2 == null) return l1;
    
            ListNode result = new ListNode(0); // initial is with a dummy value
            ListNode current = result;
    
            while(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    current.next = l1;
                    l1 = l1.next;
                 }
                else{
                    current.next = l2;
                    l2 = l2.next;
                }
                current = current.next;
            }
            if(l1 == null) current.next = l2;
            if(l2 == null) current.next = l1;
            return result.next;
        }
    }	
    

Log in to reply
 

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