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.