Java Solution for https://leetcode.com/problems/merge-two-sorted-lists/
- 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
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
Our solution passes all the test cases and it’s accepted by Leetcode & Our code runtime is 0 ms which is great.
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!
Please subscribe to my youtube channel for more such videos.