Easy
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.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
Constraints:
[0, 50]
.-100 <= Node.val <= 100
l1
and l2
are sorted in non-decreasing order.To solve the Merge Two Sorted Lists problem in Java with a Solution
class, we’ll implement a recursive approach. Here are the steps:
ListNode
class to represent a node in the linked list.Solution
class with a method named mergeTwoLists
that takes two linked lists l1
and l2
as input and returns a merged sorted list.l1
or l2
is null. In this case, return the non-null list because it’s already sorted.l1
and l2
. Let head
be the smaller value of the two heads.mergeTwoLists
with the next node of the smaller head and the other list that remained unchanged.next
pointer of the smaller head to point to the result of the recursive call.Here’s the implementation:
public class Solution {
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head;
if (l1.val < l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
public static void main(String[] args) {
Solution solution = new Solution();
// Test cases
ListNode l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);
ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
ListNode mergedList = solution.mergeTwoLists(l1, l2);
while (mergedList != null) {
System.out.print(mergedList.val + " ");
mergedList = mergedList.next;
}
System.out.println(); // newline
}
}
This implementation provides a solution to the Merge Two Sorted Lists problem in Java using a recursive approach.