Merge Sorted List (Solution For Leetcode Problem #21)
Java Solution for https://leetcode.com/problems/merge-two-sorted-lists/
Originally published at https://asyncq.com
Youtube Video
If you prefer video format: https://www.youtube.com/watch?v=29RWY7bEq-g
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 resultSolutions
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 playing with LinkedList data structure and getting confident with it. We can as the next step target more difficult LinkedList questions.
Let me know if you have some opinions on the solution in the comment section!
Bonus
- If you want to upskill your coding interview game, you should definitely check out this bestseller course ( this is in Java )
Happy Leetcoding!
Let’s connect on LinkedIn If you like this article, please check more @ https://asyncq.com/