21. Merge Two Sorted Lists

Amazon

Problem

LeetCode

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2: Input: list1 = [], list2 = [] Output: []

Example 3: Input: list1 = [], list2 = [0] Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

HackerRank

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.   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 

Explanation The first linked list is:  The second linked list is:  Hence, the merged linked list is:

Solution

Iterative - O(m+n) time - O(1) space

SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
	
	if (head1 == nullptr) return head2;
	if (head2 == nullptr) return head1;
	
	SinglyLinkedListNode head(-1);
	SinglyLinkedListNode* result = &head;
	
	while (head2 != nullptr && head1 != nullptr) {
		if (head1->data < head2->data) {
			result->next = head1;
			head1 = head1->next;
		} else {
			result->next = head2;
			head2 = head2->next;
		}
		result = result-> next;
	}
	
	while (head1 != nullptr) {
		result->next = head1;
		head1 = head1->next;
		result = result-> next;
	}
	
	while (head2 != nullptr) {
		result->next = head2;
		head2 = head2->next;
		result = result-> next;
	}
 
	result = nullptr;
	return head.next;
}

The two extra loops are unnecessary, it’s enough to point the head’s next node to the next node in the remaining tree.

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
 
        ListNode* head;
        if (list1->val <= list2->val) {
            head = list1;
            list1 = list1->next;
        } else {
            head = list2;
            list2 = list2->next;
        }
        ListNode* root = head;
 
        while(list1 && list2) {
            if (list1->val <= list2->val) {
                head->next = list1;
                list1 = list1->next;
            } else {
                head->next = list2;
                list2 = list2->next;
            }
            head = head->next;
        }
        
        if(list2) head->next = list2;
        if(list1) head->next = list1;
        return root;
    }
};