It seems that the CDC has approved the use of the Pfizer vaccine on 12-16 year old’s. Hopefully most of them will be vaccinated soon. We need to get close to 95% in order to achieve herd immunity and dramatically reduce the chances of new mutations.
While looking at a list in LeetCode, I decided to go after problem 21 Merge Two Sorted Lists. Keep in mind that you do not want to memorize the solution for a large set of problems. You want to develop a sense / intuition on how to approach different type of problems.
Now let’s get to the meat for this post.
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists. Constraints: o The number of nodes in both lists is in the range [0, 50]. o -100 <= Node.val <= 100 o Both l1 and l2 are sorted in non-decreasing (ascending) order. Related Topics: o Linked List o Recursion
In this case we are provided with two linked lists. The values in the linked lists are sorted in ascending order. We need to splice the nodes into a new linked list which will contain the elements in sorted order. The Related Topics section suggests the use of linked lists and recursion. Of course any problem that can be solved with recursion can also be solved with loops.
We will solve this problem using the Java programming language and the VSCode IDE on a Windows 10 computer. For simplicity you may consider solving the problem directly on the on-line IDE provided by LeetCode. I like to keep the test scaffold and code in the same project. Because of this, we will need to develop a simple test scaffold that will collect the information, generate the linked lists, call the method in question and display the results. Such test code IS NOT PART OF THE SOLUTION.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
}
}
We are provided with the class used to represent the linked lists and the signature for the method of interest. We will need to collect the values for the nodes and populate them into the two linked lists used as arguments.
1,2,4 1,3,4 main <<< arr1: [1, 2, 4] main <<< arr2: [1, 3, 4] main <<< l1: 1->2->4 main <<< l2: 1->3->4 main <<< l3: 1->1->2->3->4->4 main <<< arr1: null main <<< arr2: null main <<< l1: main <<< l2: main <<< l3: 0 main <<< arr1: null main <<< arr2: [0] main <<< l1: main <<< l2: 0 main <<< l3: 0 1,3,5 2,4,6 main <<< arr1: [1, 3, 5] main <<< arr2: [2, 4, 6] main <<< l1: 1->3->5 main <<< l2: 2->4->6 main <<< l3: 1->2->3->4->5->6 2,4,6 1,3,5,7 main <<< arr1: [2, 4, 6] main <<< arr2: [1, 3, 5, 7] main <<< l1: 2->4->6 main <<< l2: 1->3->5->7 main <<< l3: 1->2->3->4->5->6->7 1,3,5,7 2,4,6 main <<< arr1: [1, 3, 5, 7] main <<< arr2: [2, 4, 6] main <<< l1: 1->3->5->7 main <<< l2: 2->4->6 main <<< l3: 1->2->3->4->5->6->7 1,3,5,7,9,11 2,4 main <<< arr1: [1, 3, 5, 7, 9, 11] main <<< arr2: [2, 4] main <<< l1: 1->3->5->7->9->11 main <<< l2: 2->4 main <<< l3: 1->2->3->4->5->7->9->11
The first three test examples are provided by LeetCode. The rest I created to further check our solutions.
We are provided with two lines of integers separated by ‘,’s. The first line represents the contents for the first linked list while the second line for the second linked list.
Apparently the values are read from the input and are used to populate a couple of arrays.
The two linked lists are created and populated. The values seem to match so far.
The method of interest is called and the results are displayed. The results are collected in a third linked list.
It is not obvious by what we just saw but we have two implementations for the method of interest. Since the lists are modified, for simplicity I just commented out the first implementation. This will become clear when we take a look at the test scaffold.
/**
* Test scaffold.
* @throws Exception
*
* !!! NOT PART OF SOLUTION !!!
*/
public static void main(String[] args) throws Exception {
// **** ****
int[] arr1 = null;
int[] arr2 = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read array with values for first list ****
try {
arr1 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
} catch (Exception NumberFormatException) {
// ???? ????
// System.err.println("main <<< NumberFormatException arr1");
}
// **** read array with values for second list ****
try {
arr2 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
} catch (Exception NumberFormatException) {
// ???? ????
// System.err.println("main <<< NumberFormatException arr2");
}
// **** close buffered reader ****
br.close();
// ???? display arrays ????
System.out.println("main <<< arr1: " + Arrays.toString(arr1));
System.out.println("main <<< arr2: " + Arrays.toString(arr2));
// **** generate first linked list ****
ListNode l1 = populate(arr1);
// **** generate second linked list ****
ListNode l2 = populate(arr2);
// ???? display first linked list ????
System.out.print("main <<< l1: ");
display(l1);
System.out.println();
// ???? display second linked list ????
System.out.print("main <<< l2: ");
display(l2);
System.out.println();
// **** merged the two lists ****
// ListNode l3 = mergeTwoLists0(l1, l2);
ListNode l3 = mergeTwoLists(l1, l2);
// ???? display result linked list ????
System.out.print("main <<< l3: ");
display(l3);
System.out.println();
}
The test scaffold seems to closely match our previous description. Once we have the array of int[]s we populate and display the two input linked lists. Note that either or both may be empty. Also note that the first implementation has been commented out. The result returned by the method of interest is saved in l3 and then is displayed.
/**
* Populate linked list with the specified array values.
*
* !!! NOT PART OF SOLUTION !!!
*/
static ListNode populate(int[] arr) {
// **** sanity ckeck(s) ****
if (arr == null || arr.length == 0)
return null;
// **** initialization ****
ListNode h = null;
// **** traverse array adding nodes to the linked list ****
for (int i = arr.length - 1; i >= 0; i--) {
h = new ListNode(arr[i], h);
}
// **** return head of linked list ****
return h;
}
This method creates and populates a linked list with the contents of the specified array. We have seen this method in different posts in this blog.
/**
* Display linked list.
*
* !!! NOT PART OF SOLUTION !!!
*/
static void display(ListNode head) {
// **** sanity check(s) ****
if (head == null)
return;
// **** traverse the link list ****
for (ListNode p = head; p != null; p = p.next) {
System.out.print(p.val);
if (p.next != null)
System.out.print("->");
}
}
This method is used to display the input and output linked lists. We have seen this method in different posts in this blog.
/**
* Merge two sorted linked lists and return it as a sorted list.
* Recursive approach.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.1 MB, less than 77.21% of Java online submissions.
*
*/
static ListNode mergeTwoLists0(ListNode l1, ListNode l2) {
// **** sanity check(s) ****
if (l1 != null && l2 == null)
return l1;
if (l1 == null && l2 != null)
return l2;
// **** initialization ****
ListNode l3 = null;
// **** end condition ****
if (l1 == null && l2 == null)
return null;
// **** build merged list ****
if (l1.val <= l2.val) {
l3 = l1;
l1 = l1.next;
} else {
l3 = l2;
l2 = l2.next;
}
// **** recursion ****
l3.next = mergeTwoLists0(l1, l2);
// **** return l3 ****
return l3;
}
This is the first implementation of the method of interest. It uses the recursive approach as suggested.
We start by performing some sanity checks. We the initialize the l3 linked list which will be used to build our merged linked list.
The end condition follows. We want to continue while there are nodes in either linked list to process.
We then build the linked list. We must process the smallest node from either list. Once we have it and skip it we recursively make a call to continue building the resulting linked list.
When the recursive call return, we need to generate the resulting linked list. We then return the updated l3 linked list.
After testing the code I submitted it to LeetCode for evaluation. Take a look at the comments section to find out the results. Not bad.
/**
* Merge two sorted linked lists and return it as a sorted list.
* Non-recursive approach.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.2 MB, less than 77.21% of Java online submissions.
*/
static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// **** sanity checks ****
if (l1 != null && l2 == null)
return l1;
if (l1 == null && l2 != null)
return l2;
if (l1 == null && l2 == null)
return null;
// **** initialization ****
ListNode dummy = new ListNode(-1);
ListNode head = dummy;
// **** loop traversing the linked lists ****
while (l1 != null && l2 != null) {
// **** select next node ****
if (l1.val <= l2.val) {
dummy.next = l1;
l1 = l1.next;
} else {
dummy.next = l2;
l2 = l2.next;
}
// **** move dummy pointer forward ****
dummy = dummy.next;
}
// **** append list (if needed) ****
if (l1 != null)
dummy.next = l1;
else if (l2 != null)
dummy.next = l2;
// **** return merged linked list (skip dummy node) ****
return head.next;
}
In this approach we will not use recursion. Instead we will use a while loop.
We create a linked list in which we will construct the result. We then enter a loop. The loop is similar to what we had in the previous implementation.
Note that we have to update the nodes in the resulting linked list and we have to move the pointer forward.
After the loop we need to take care of the remaining node(s) in one of the lists (if any).
We are ready to return the result. Note that since we created a dummy node we need to return the linked list that sips it.
Of interest, take a look at the comment section in this implementation and compare the execution results with the previous implementation. They are quite similar. Apparently the number and complexity of the tests did not affect the fact that one approach used recursion and the other a loop.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John