Merge two sorted lists amazon
Twitter13FacebookLinkedInBufferRedditTumblr 13 SHARES Linked lists are quite like arrays in their linear properties. We can merge two sorted arrays to form an overall sorted array. In this problem, we have to merge two sorted linked lists in placeto return a new list which contains elements of both lists in a sorted fashion. Show Table of Contents
Example
ApproachThe simplest way to do it would be to use the two-pointer technique. Create a new empty list. Append the smaller elements among both the pointers and increment the corresponding pointer. This is a good approach but requires the creation of an extra list that consumes space. The Optimal Approach should consume constant space only in order to do an in-place sorting. We can follow the iterative approach. We already have the nodes stored in both the lists. Create a new list pointer and its subsequent next pointers should point to predefined nodes in the memory. In this process, we create no new nodes. Algorithm(Naive Approach)
See also Count pair with Given Sum Algorithm(Optimal)
ImplementationC++ Program to Merge Two Sorted ListsNaive Approach#includeOptimal Method#includeJava Program to Merge Two Sorted ListsNaive Approachclass listNode { int value; listNode next; listNode(int x) { value = x; next = null; } } class merge_two_sorted_lists { public static void print(listNode head) { while(head != null) { System.out.print(head.value + " "); head = head.next; } return; } public static listNode mergeTwoSortedLists(listNode l1 , listNode l2) { if(l1 == null) return l2; if(l2 == null) return l1; listNode temp; if(l1.value < l2.value) { temp = new listNode(l1.value); temp.next = mergeTwoSortedLists(l1.next , l2); } else { temp = new listNode(l2.value); temp.next = mergeTwoSortedLists(l1 , l2.next); } return temp; } public static void main(String args[]) { listNode l1 = new listNode(1); l1.next = new listNode(2); l1.next.next = new listNode(9); listNode l2 = new listNode(1); l2.next = new listNode(3); l2.next.next = new listNode(4); print(mergeTwoSortedLists(l1 , l2)); } }Optimal Methodclass listNode { int value; listNode next; listNode(int x) { value = x; next = null; } } class merge_two_sorted_lists { public static void print(listNode head) { while(head != null) { System.out.print(head.value + " "); head = head.next; } return; } public static listNode mergeTwoSortedLists(listNode l1 , listNode l2) { listNode dummy_head = new listNode(-1) , prehead = dummy_head; while(l1 != null && l2 != null) { if(l1.value < l2.value) { dummy_head.next = l1; l1 = l1.next; } else { dummy_head.next = l2; l2 = l2.next; } dummy_head = dummy_head.next; } dummy_head.next = ((l1 != null) ? l1 : l2); return prehead.next; } public static void main(String args[]) { listNode l1 = new listNode(1); l1.next = new listNode(2); l1.next.next = new listNode(9); listNode l2 = new listNode(1); l2.next = new listNode(3); l2.next.next = new listNode(4); print(mergeTwoSortedLists(l1 , l2)); } } 1 1 2 3 4 9Complexity AnalysisTime Complexity to Merge Two Sorted ListsO(N + M), where N and M are the lengths of the two lists. We traverse both the lists once in both approaches, so both the algorithms are linear. See also Valid Palindrome Leetcode Solution Space Complexity to Merge Two Sorted ListsIn the Optimal approach, it is important to understand that we only manipulate the pointers. So, the constant space for variables accounts for memory usage. Therefore, the optimal method has a space complexity of O(1). O(N + M) space is used in the naive approach discussed. Twitter13FacebookLinkedInBufferRedditTumblr 13 SHARES |