X This site uses cookies. By continuing, you agree to their use. Learn more, including how to control cookies.
You’re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty. Input Format You have to complete the SinglyLinkedListNode MergeLists(SinglyLinkedListNode headA, SinglyLinkedListNode headB) method which takes two arguments – the heads of the two sorted linked lists to merge. You should NOT read any input from stdin/console. The input is handled by the code in the editor and the format is as follows: The first line contains an integer t, denoting the number of test cases.
The format for each test case is as follows: The first line contains an integer n, denoting the length of the first linked list.
The next n lines contain an integer each, denoting the elements of the linked list.
The next line contains an integer m, denoting the length of the second linked list.
The next m lines contain an integer each, denoting the elements of the second linked list. Constraints - 1 <= t <= 10
- 1 <= n <= 1000
- 1 <= list’i <= 1000, where list’i is the i’th element of the list.
Output Format Change the next pointer of individual nodes so that nodes from both lists are merged into a single list. Then return the head of this merged list. Do NOT print anything to stdout/console. The output is handled by the editor and the format is as follows: For each test case, print in a new line, the linked list after merging them separated by spaces. Sample Input Sample Output Explanation The first linked list is: 1 -> 2 -> 3 -> NULL The second linked list is: 3 -> 4 -> NULL Hence, the merged linked list is: 1 -> 2 -> 3 -> 3 -> 4 -> NULL Code: static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
if(head1 == null) {
return head2;
}
if(head2 == null) {
return head1;
}
if(head1.data < head2.data) {
head1.next = mergeLists(head1.next, head2);
return head1;
} else {
head2.next = mergeLists(head1, head2.next);
return head2;
}
}
Hope you guys understand the simple solution of inserting a node at tail in linked list in java. For practicing the question link is given https://www.hackerrank.com/challenges/merge-two-sorted-linked-lists/problem In next blog we will see other operations on linked list till then Bye Bye..! Thanks for reading…! Happy Coding..! Thank You…! Write a SortedMerge() function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. SortedMerge() should return the new list. The new list should be made by splicing together the nodes of the first two lists. For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20. There are many cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally, there’s the problem of starting the result list empty, and building it up while going through ‘a’ and ‘b’.
Method 1 (Using Dummy Nodes)
The strategy here uses a temporary dummy node as the start of the result list. The pointer Tail always points to the last node in the result list, so appending new nodes is easy. The dummy node gives the tail something to point to initially when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’, and adding it to the tail. When
We are done, the result is in dummy.next. The below image is a dry run of the above approach: Below is the implementation of the above approach:
|
void MoveNode(Node** destRef, Node** sourceRef);
Node* SortedMerge(Node* a, Node* b)
MoveNode(&(tail->next), &a);
MoveNode(&(tail->next), &b);
void MoveNode(Node** destRef, Node** sourceRef)
Node* newNode = *sourceRef;
*sourceRef = newNode->next;
newNode->next = *destRef;
void push(Node** head_ref, int new_data)
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
void printList(Node *node)
cout << "Merged Linked List is: \n";
|
|
void MoveNode(struct Node** destRef, struct Node** sourceRef);
struct Node* SortedMerge(struct Node* a, struct Node* b)
struct Node* tail = &dummy;
MoveNode(&(tail->next), &a);
MoveNode(&(tail->next), &b);
void MoveNode(struct Node** destRef, struct Node** sourceRef)
struct Node* newNode = *sourceRef;
*sourceRef = newNode->next;
newNode->next = *destRef;
void push(struct Node** head_ref, int new_data)
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
void printList(struct Node *node)
printf("%d ", node->data);
printf("Merged Linked List is: \n");
|
|
public void addToTheLast(Node node)
while (temp.next != null)
System.out.print(temp.data + " ");
public static void main(String args[])
MergeLists llist1 = new MergeLists();
MergeLists llist2 = new MergeLists();
llist1.addToTheLast(new Node(5));
llist1.addToTheLast(new Node(10));
llist1.addToTheLast(new Node(15));
llist2.addToTheLast(new Node(2));
llist2.addToTheLast(new Node(3));
llist2.addToTheLast(new Node(20));
llist1.head = new Gfg().sortedMerge(llist1.head,
Node sortedMerge(Node headA, Node headB)
Node dummyNode = new Node(0);
if(headA.data <= headB.data)
|
|
def __init__(self, data):
print(temp.data, end=" ")
def addToList(self, newData):
def mergeLists(headA, headB):
if headA.data <= headB.data:
listA.head = mergeLists(listA.head, listB.head)
print("Merged Linked List is:")
|
|
public void addToTheLast(Node node)
while (temp.next != null)
Console.Write(temp.data + " ");
public static void Main(String []args)
MergeLists llist1 = new MergeLists();
MergeLists llist2 = new MergeLists();
llist1.addToTheLast(new Node(5));
llist1.addToTheLast(new Node(10));
llist1.addToTheLast(new Node(15));
llist2.addToTheLast(new Node(2));
llist2.addToTheLast(new Node(3));
llist2.addToTheLast(new Node(20));
llist1.head = new Gfg().sortedMerge(llist1.head,
public Node sortedMerge(Node headA, Node headB)
Node dummyNode = new Node(0);
if(headA.data <= headB.data)
|
|
while (temp.next != null)
document.write(temp.data + " ");
function sortedMerge(headA,headB)
let dummyNode = new Node(0);
if(headA.data <= headB.data)
let llist1 = new LinkedList();
let llist2 = new LinkedList();
llist1.addToTheLast(new Node(5));
llist1.addToTheLast(new Node(10));
llist1.addToTheLast(new Node(15));
llist2.addToTheLast(new Node(2));
llist2.addToTheLast(new Node(3));
llist2.addToTheLast(new Node(20));
llist1.head = sortedMerge(llist1.head,
document.write("Merged Linked List is:<br>")
|
Output : Merged Linked List is:
2 3 5 10 15 20Method 2 (Using Local References)
This solution is structurally very similar to the above, but it avoids using a dummy node. Instead, it maintains a struct node** pointer, lastPtrRef, that always points to the last pointer of the result list. This solves the same case that the dummy node did — dealing with the result list when it is empty. If you are trying to build up a list at its tail, either the dummy node or the struct node** “reference” strategy can be used (see Section 1 for details).
|
Node* SortedMerge(Node* a, Node* b)
Node** lastPtrRef = &result;
MoveNode(lastPtrRef, &a);
MoveNode(lastPtrRef, &b);
lastPtrRef = &((*lastPtrRef)->next);
|
|
struct Node* SortedMerge(struct Node* a, struct Node* b)
struct Node* result = NULL;
struct Node** lastPtrRef = &result;
MoveNode(lastPtrRef, &a);
MoveNode(lastPtrRef, &b);
lastPtrRef = &((*lastPtrRef)->next);
|
|
Node SortedMerge(Node a, Node b)
Node lastPtrRef = result;
lastPtrRef = ((lastPtrRef).next);
|
|
lastPtrRef = ((lastPtrRef).next);
|
|
Node SortedMerge(Node a, Node b)
Node lastPtrRef = result;
lastPtrRef = ((lastPtrRef).next);
|
|
function SortedMerge(a,b)
lastPtrRef = ((lastPtrRef).next);
|
Method 3 (Using Recursion)
Merge is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code. You probably wouldn’t want to use the recursive version for production code, however, because it will use stack space which is proportional to the length of the lists.
|
Node* SortedMerge(Node* a, Node* b)
result->next = SortedMerge(a->next, b);
result->next = SortedMerge(a, b->next);
|
|
struct Node* SortedMerge(struct Node* a, struct Node* b)
struct Node* result = NULL;
result->next = SortedMerge(a->next, b);
result->next = SortedMerge(a, b->next);
|
|
public Node SortedMerge(Node A, Node B)
A.next = SortedMerge(A.next, B);
B.next = SortedMerge(A, B.next);
|
|
def __init__(self, data):
print(temp.data, end="->")
def append(self, new_data):
new_node = Node(new_data)
def mergeLists(head1, head2):
if head1.data <= head2.data:
temp.next = mergeLists(head1.next, head2)
temp.next = mergeLists(head1, head2.next)
if __name__ == '__main__':
list3.head = mergeLists(list1.head, list2.head)
print(" Merged Linked List is : ", end="")
|
|
public Node sortedMerge(Node A, Node B)
A.next = sortedMerge(A.next, B);
B.next = sortedMerge(A, B.next);
|
|
function SortedMerge( A, B) {
A.next = SortedMerge(A.next, B);
B.next = SortedMerge(A, B.next);
|
Time Complexity: Since we are traversing through the two lists fully. So, the time complexity is O(m+n) where m and n are the lengths of the two lists to be merged. Method 4 (Reversing The Lists) This idea involves first reversing both the given lists and after reversing, traversing both the lists till the end and then comparing the nodes of both the lists and inserting the node with a larger value at the beginning of the result list. And in this way we will get the resulting list in increasing order. 1) Initialize result list as empty: head = NULL.
2) Let 'a' and 'b' be the heads of first and second list respectively.
3) Reverse both the lists.
4) While (a != NULL and b != NULL)
a) Find the larger of two (Current 'a' and 'b')
b) Insert the larger value of node at the front of result list.
c) Move ahead in the list of larger node.
5) If 'b' becomes NULL before 'a', insert all nodes of 'a'
into result list at the beginning.
6) If 'a' becomes NULL before 'b', insert all nodes of 'b'
into result list at the beginning. Below is the implementation of above solution.
|
Node* reverseList(Node* head)
Node* rest = reverseList(head->next);
Node* sortedMerge(Node* a, Node* b)
while (a != NULL && b != NULL) {
void printList(struct Node* Node)
Node* temp = (Node *)malloc(sizeof(Node));
a->next->next = newNode(15);
a->next->next->next = newNode(40);
b->next->next = newNode(20);
printf("List A before merge: \n");
printf("\nList B before merge: \n");
printf("\nMerged Linked List is: \n");
|
|
Node* reverseList(Node* head)
Node* rest = reverseList(head->next);
Node* sortedMerge(Node* a, Node* b)
while (a != NULL && b != NULL) {
void printList(struct Node* Node)
cout << Node->key << " ";
a->next->next = newNode(15);
a->next->next->next = newNode(40);
b->next->next = newNode(20);
cout << "List A before merge: \n";
cout << "\nList B before merge: \n";
cout << "\nMerged Linked List is: \n";
|
|
static Node reverseList(Node head)
Node rest = reverseList(head.next);
static Node sortedMerge(Node a, Node b)
while (a != null && b != null) {
static void printList(Node Node)
System.out.print(Node.key+ " ");
static Node newNode(int key)
public static void main(String[] args)
a.next.next = newNode(15);
a.next.next.next = newNode(40);
b.next.next = newNode(20);
System.out.print("List A before merge: \n");
System.out.print("\nList B before merge: \n");
System.out.print("\nMerged Linked List is: \n");
|
|
using System.Collections.Generic;
static Node reverseList(Node head)
Node rest = reverseList(head.next);
static Node sortedMerge(Node a, Node b)
while (a != null && b != null) {
static void printList(Node Node)
Console.Write(Node.key+ " ");
static Node newNode(int key)
public static void Main(String[] args)
a.next.next = newNode(15);
a.next.next.next = newNode(40);
b.next.next = newNode(20);
Console.Write("List A before merge: \n");
Console.Write("\nList B before merge: \n");
Console.Write("\nMerged Linked List is: \n");
|
Output: List A before merge:
5 10 15 40
List B before merge:
2 3 20
Merged Linked List is:
2 3 5 10 15 20 40 Time Complexity: Since we are traversing through the two lists fully. So, the time complexity is O(m+n) where m and n are the lengths of the two lists to be merged. This method is contributed by Mehul Mathur(mathurmehul01). This idea is similar to this post. Please refer below post for simpler implementations :
Merge two sorted lists (in-place)
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Please write comments if you find the above code/algorithm incorrect, or find better ways to solve the same problem.
| 
