Java Solution for https://leetcode.com/problems/merge-two-sorted-lists/

Understanding Problem

• We have been given two sorted singly linked lists and our job is to merge these two lists such that the result list should also be sorted.
• For example,

l1 = [2,3,4,5] & l2=[1,6,7,8]
result = [1,2,3,4,5,6,7,8]

My Thought About Solution

• The solution for this problem looks simple, we can traverse both the list and compare the node value, and based on it we can sort and write the result to result_list.
• Data structure: We need LinkedList to store sorted values from the input list
  Time-complexity: O(N or M) where N & M is the length of the is the input list, and traversal would end at whichever list we choose as the first list for comparison
  Space-complexity: O(N+M), since the result list will hold all the input elements from the first and second LinkedList

Pseudocode

1: Create Result LinkedList
2: Store start of the Result LinkedList in Head node. 
   ( ListNode head = result; )
3: While ( l1 and l2 not null )
   then we compare 
      l1.val is less than l2.val 
        result.next = l1
        l1=l1.next
      if l1.val is equal or greater than l2.val
        result.next = l2;
        l2=l2.next;
      
     result = result.next;
4: if while loop terminated then , either l1 is finished traversing or l2 is finished traversing.
   if l1 is finished traversing then
     result.next = l2   else 
     result.next = l2;5: return head.next     // return head of the result

Solutions

Result

Our solution passes all the test cases and it’s accepted by Leetcode & Our code runtime is 0 ms which is great.

Conclusion

This Leetcode problem is a good start to play with LinkedList data structure and get confident with it. We can as a next step target more difficult Linkedlist problems

Let me know if you have some opinions on the solution in the comment section!

Bonus Tip

• If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )

Happy Leetcoding!

Please subscribe to my youtube channel for more such videos.