Question

Please solve using java.

21. Merge Two Sorted Lists Easy 2705 396 ♡ Favorite Sha * Definition for singly-linked list. * public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. class Solution { public ListNode merge TwoLists(ListNode li, ListNode 12) { 10 Example: Input: 1->2->4, 1-3-4 Output: 1->1->2->3->4->4 Accepted 699.5K Submissions 1.4M Contributor Companies a Related Topics Similar Questions

Answer 1

Here is the completed code for this problem. This code alters the input lists by rearranging the links, not creating new nodes. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

class Solution {

      // required method

      public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

            // creating a ListNode reference to store the head of sorted list

            ListNode root = null;

            // creating a ListNode reference to store the current node of sorted

            // list

            ListNode current = null;

            // looping as long as l1 and l2 are not null

            while (l1 != null && l2 != null) {

                  // comparing value of l1 with value of l2

                  if (l1.val <= l2.val) {

                        // if current is null,setting l1 as current & root nodes

                        if (current == null) {

                              current = l1;

                              root = current;

                        } else {

                              // otherwise, setting l1 as next node of current and

                              // advancing current

                              current.next = l1;

                              current = current.next;

                        }

                        // moving to next node in l1

                        l1 = l1.next;

                  } else {

                        // doing the same with l2

                        if (current == null) {

                              current = l2;

                              root = current;

                        } else {

                              current.next = l2;

                              current = current.next;

                        }

                        l2 = l2.next;

                  }

            }

            // after the loop, if l1 is not null, appending l1 to current, if l2 is

            // not null, appending l2 to current. this is needed in case lists have

            // unequal lengths

            if (l1 != null) {

                  if (current == null) {

                        current = l1;

                        root = current;

                  } else {

                        current.next = l1;

                  }

            }

            if (l2 != null) {

                  if (current == null) {

                        current = l2;

                        root = current;

                  } else {

                        current.next = l2;

                  }

            }

            //returning head of root node of merged list

            return root;

      }

}

Answer 2

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        
        //Define a new Node
        ListNode answer = new ListNode();
        ListNode newNode = answer;        
        //If list1 has no element then add list2 to new node
        if (list1 == null)           return newNode.next = list2;        
        //If list2 has no element then add list1 to new node
        if (list2 == null)            return newNode.next = list1;        
        
        //Use Merge sort logic to merge nodes value
        while (list1 != null && list2 != null)
        {            if (list1.val <= list2.val)
            {
                newNode.next = list1;
                list1 = list1.next;
            }            else 
            {
                newNode.next = list2;
                list2 = list2.next;
            }
            newNode = newNode.next;
        }    
        //If any node left in list1
        if (list1 != null)
            newNode.next = list1;     
        //If any node left in list2
        if (list2 != null)
            newNode.next = list2;        
        return answer.next;

    }
}