Merge two sorted linked lists and return it as a new list.
The new list should be made by splicing together the nodes of the first two lists, and should also be sorted.
For example, given following linked lists :
5 -> 8 -> 20
4 -> 11 -> 15The merged list should be :
4 -> 5 -> 8 -> 11 -> 15 -> 20
import java.util.*;
/*
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; next = null; }
}
*/
public class Solution {
/*
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr1 = new int[n];
int[] arr2 = new int[m];
for(int i = 0; i < n; i++)
arr1[i] = sc.nextInt();
for(int i = 0; i < m; i++)
arr2[i] = sc.nextInt();
ListNode head1 = new ListNode(arr1[0]);
ListNode head2 = new ListNode(arr2[0]);
ListNode temp1 = head1;
ListNode temp2 = head2;
for(int i = 1; i < n; i++)
{
temp1.next = new ListNode(arr1[i]);
temp1 = temp1.next;
}
for(int i = 1; i < m; i++)
{
temp2.next = new ListNode(arr2[i]);
temp2 = temp2.next;
}
ListNode res = mergeTwoLists(head1, head2);
while(res != null)
{
System.out.print(res.val + " ");
res = res.next;
}
sc.close();
}
*/
public static ListNode mergeTwoLists(ListNode A, ListNode B) {
if(A == null)
return B;
if(B == null)
return A;
ListNode res = new ListNode(0);
ListNode resPtr = res;
while(A != null && B != null)
{
if(A.val <= B.val)
{
res.next = A;
A = A.next;
}
else
{
res.next = B;
B = B.next;
}
res = res.next;
}
while(A != null)
{
res.next = A;
res = res.next;
A = A.next;
}
while(B != null)
{
res.next = B;
res = res.next;
B = B.next;
}
return resPtr.next;
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
*/
ListNode* mergeTwoLists(ListNode* A, ListNode* B) {
if(A == NULL)
return B;
if(B == NULL)
return A;
ListNode* res = new ListNode(0);
ListNode* resPtr = res;
while(A != NULL && B != NULL)
{
if(A->val <= B->val)
{
res->next = A;
A = A->next;
}
else
{
res->next = B;
B = B->next;
}
res = res->next;
}
while(A != NULL)
{
res->next = A;
res = res->next;
A = A->next;
}
while(B != NULL)
{
res->next = B;
res = res->next;
B = B->next;
}
return resPtr->next;
}
/*
int main() {
int n, m;
cin >> n >> m;
vector<int> arr1(n);
vector<int> arr2(m);
for(int i = 0; i < n; i++)
cin >> arr1[i];
for(int i = 0; i < m; i++)
cin >> arr2[i];
ListNode* head1 = new ListNode(arr1[0]);
ListNode* head2 = new ListNode(arr2[0]);
ListNode* temp1 = head1;
ListNode* temp2 = head2;
for(int i = 1; i < n; i++)
{
temp1->next = new ListNode(arr1[i]);
temp1 = temp1->next;
}
for(int i = 1; i < m; i++)
{
temp2->next = new ListNode(arr2[i]);
temp2 = temp2->next;
}
ListNode* res = mergeTwoLists(head1, head2);
while(res != NULL)
{
cout << res->val << " ";
res = res->next;
}
return 0;
}
*/step-by-step explanation
First, we check if either of the input lists is null. If one of them is null, we simply return the other list, since the result of merging a null list with a non-null list is just the non-null list.
if(A == null)
return B;
if(B == null)
return A;Next, we create a new ListNode object named res to serve as the head of our result list, and another ListNode object named resPtr to keep track of the current end of the result list as we merge the input lists.
ListNode res = new ListNode(0);
ListNode resPtr = res;We use a while loop to merge the input lists. The loop continues as long as both A and B are not null. At each iteration, we compare the first elements of A and B, and add the smaller element to the end of the result list. We then move the pointer of the corresponding input list to the next element.
while(A != null && B != null)
{
if(A.val <= B.val)
{
res.next = A;
A = A.next;
}
else
{
res.next = B;
B = B.next;
}
res = res.next;
}At this point, either A or B may still have some elements left over. We use two more while loops to add any remaining elements to the end of the result list.
while(A != null)
{
res.next = A;
res = res.next;
A = A.next;
}
while(B != null)
{
res.next = B;
res = res.next;
B = B.next;
}Finally, we return the next node after resPtr, which is the head of the merged list.
return resPtr.next;