Instagram
youtube
Facebook
Twitter

Merge Two Sorted Linked Lists| Linked List

TASK(easy)

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

headA refers to 1->3->7->NULL
headB refers to 1->2->NULL

The new list is 1->1->2->3->7->NULL

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 t, the number of test cases. The format for each test case is as follows:The first line contains an integer n, the length of the first linked list.
The next n lines contain an integer each, the elements of the linked list.
The next line contains an integer m, the length of the second linked list.
The next m lines contain an integer each, the elements of the second linked list.

Constraints

1<=t<=10
1<=n, m<=1000
1<=list[i]<=1000, where list[i] is the ith element of the list.

Sample Input

1

3

1

2

3

2

3

4

Sample Output

1 2 3 3 4

SOLUTION 1

def mergeLists(head1, head2):

    l, result = [], SinglyLinkedList()

    while head1:

        l.append(head1.data)

        head1 = head1.next

    while head2:

        l.append(head2.data)

        head2 = head2.next

    for data in sorted(l):

        result.insert_node(data)

    return result.head

SOLUTION 2

def mergeLists(head1, head2):

    result = SinglyLinkedList()

    while head1 or head2:

        if not head1:

            result.insert_node(head2.data)

            head2 = head2.next

        elif not head2:

            result.insert_node(head1.data)

            head1 = head1.next

        elif head1 and head2:

            if head1.data <= head2.data:

                result.insert_node(head1.data)

                head1 = head1.next

            else:

                result.insert_node(head2.data)

                head2 = head2.next

    return result.head

EXPLANATION STEPS

 1.Initialize: Create a dummy node and pointers for both lists.

2.Compare & Merge: Iterate through both lists, appending the smaller node to the merged list.

 3.Attach Remaining Nodes: If one list is exhausted, attach the remaining nodes from the other list.

4.Return: Return the merged list starting from .next.