Merge two sorted linked lists HackerRank Solution

Merge two sorted linked lists HackerRank Solution

by

In this Merge two sorted linked lists HackerRank solution, Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty.

Example
 refers to 
 refers to 

The new list is 

Function Description

Complete the mergeLists function in the editor below.

mergeLists has the following parameters:

  • SinglyLinkedListNode pointer headA: a reference to the head of a list
  • SinglyLinkedListNode pointer headB: a reference to the head of a list

Returns

  • SinglyLinkedListNode pointer: a reference to the head of the merged list

Input Format

The first line contains an integer , the number of test cases.

The format for each test case is as follows:

The first line contains an integer , the length of the first linked list.
The next  lines contain an integer each, the elements of the linked list.
The next line contains an integer , the length of the second linked list.
The next  lines contain an integer each, the elements of the second linked list.

Constraints

  • , where  is the  element of the list.

Sample Input

1
3
1
2
3
2
3
4

Sample Output

1 2 3 3 4

Merge two sorted linked lists HackerRank solution

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in Python

def mergeLists(head1, head2):
    dummy = SinglyLinkedListNode(0)
    nHead = dummy
    node1, node2 = head1, head2
   
    while node1 and node2:
        if node1.data > node2.data:
            dummy.next = node2
            node2 = node2.next
        else:
            dummy.next = node1
            node1 = node1.next
           
        dummy = dummy.next
   
    if node1:
        dummy.next = node1
    if node2:
        dummy.next = node2
   
    return nHead.next

Problem Solution in C++

SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    if(head1==nullptr) return head2;
    if(head2==nullptr) return head1;
   
    SinglyLinkedListNode *head;
    if(head1->data<=head2->data) {
        head = head1;
        head1 = head1->next;
    } else {
        head = head2;
        head2 = head2->next;
    }


    SinglyLinkedListNode *cur = head;
    while(head1!=nullptr && head2!=nullptr) {
        if(head1->data<=head2->data) {
            cur->next = head1;
            cur = head1;
            head1 = head1->next;
        } else {
            cur->next = head2;
            cur = head2;
            head2 = head2->next;
        }
    }
   
    if(head1!=nullptr) cur->next=head1;
    else if(head2!=nullptr) cur->next=head2;
   
    return head;
}

Problem Solution in JavaScript

function mergeLists(l1, l2) {
if (!l1 && !l2) return null
    if (!l1) return l2
    if (!l2) return l1
 
    if (l1.data < l2.data) {
        l1.next = mergeLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeLists(l1, l2.next)
        return l2
    }
}

Problem Solution in Java

SinglyLinkedList sResult = new SinglyLinkedList();
        List<Integer> integerList = new ArrayList<Integer>();
        SinglyLinkedListNode nTmp = head1;
        while(nTmp != null){
            integerList.add(nTmp.data);
            nTmp = nTmp.next;
        }
        nTmp = head2;
        while(nTmp != null){
            integerList.add(nTmp.data);
            nTmp = nTmp.next;
        }
        integerList.stream()
            .sorted()
            .forEach(p->{
                sResult.insertNode(p);
            });
       
        return sResult.head;

Solve original Problem on HackerRank here. Checkout more HackerRank Problems

Leave a Comment