Question

using the single linked list code written in the class or in the lab, write and test the follow function: Merge() 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.
With the main function please

Answer 1

//The main class
class MergeList {

Node head; // head of list
static Node a, b;

//Node class
static class Node {

int element;
Node next;

// Constructor to create a new node
Node(int d) {
element = d;
next = null;
}
}

void printlist(Node node) {
while (node != null) {
System.out.print(node.element + " ");
node = node.next;
}
}

Node sortMerge(Node node1, Node node2) {

// Here we will check whether both the list are null or not.
if (node1 == null && node2 == null) {
return null;
}

// sortResultant node
Node sortRes = null;

// Now we will compare and merge the elements of both the list.
while (node1 != null && node2 != null) {

// We will compare current element of both lists
if (node1.element >= node2.element) {
Node temp = node1.next;
node1.next = sortRes;
sortRes = node1;
node1 = temp;
} else {
Node temp = node2.next;
node2.next = sortRes;
sortRes = node2;
node2 = temp;
}
}

// If second list reached end, but first list has
// nodes. Add remaining nodes of first list at the
// front of sortResult list
while (node1 != null) {
Node temp = node1.next;
node1.next = sortRes;
sortRes = node1;
node1 = temp;
}

// If first list reached end, but second list has
// node. Add remaining nodes of first list at the
// front of sortResult list
while (node2 != null) {
Node temp = node2.next;
node2.next = sortRes;
sortRes = node2;
node2 = temp;
}

return sortRes;

}

public static void main(String[] args) {

MergeList list = new MergeList();
Node sortResult = null;

//Create two linked list
list.a = new Node(5);
list.a.next = new Node(10);
list.a.next.next = new Node(15);

list.b = new Node(2);
list.b.next = new Node(3);
list.b.next.next = new Node(20);

System.out.println("List a before merge :");
list.printlist(a);
System.out.println("");
System.out.println("List b before merge :");
list.printlist(b);

// Cal the function to merge the list in increasing order.
sortResult = list.sortedmerge(a, b);
System.out.println("");
System.out.println("Merged linked list : ");
list.printlist(sortResult);

}
}