DATA STRUCTURE AND ALGORITHAMS

DATA STRUCTURE AND ALGORITHAMS. ISE -1 ACTIVITY-2.

Name: Nilesh Prakash Pawar Roll no.: 2013 URN NO. : 21101014.

How to merge two un sorted singly linked list ?. Single linked list = A singly linked list is a type of linked list that is unidirectional , that is, it can be traversed in only one direction from head to the last node (tail). Each element in a linked list is called a node . A single node contains data and a pointer to the next node which helps in maintaining the structure of the list..

Efficient Approach : To optimize the above method we will concatenate the two linked lists and then sort it using any sorting algorithm. Below are the steps: Concatenate the two lists by traversing the first list until we reach it’s a tail node and then point the next of the tail node to the head node of the second list. Store this concatenated list in the first list. Sort the above-merged linked list. Here, we will use a bubble sort. So, if node->next->data is less then node->data, then swap the data of the two adjacent node..

program. // C++ program for the above approach #include <bits/ stdc ++.h> using namespace std; // Create structure for a node struct node; // Function to print the linked list void setData (node* head) { node* tmp ; // Store the head of the linked // list into a temporary node* // and iterate tmp = head; while ( tmp != NULL) {.

cout << tmp ->data << " -> "; tmp = tmp ->next; } } // Function takes the head of the // LinkedList and the data as // argument and if no LinkedList // exists, it creates one with the // head pointing to first node. // If it exists already, it appends // given node at end of the last node node* getData (node* head, int num) { // Create a new node node* temp = new node; node* tail = head; // Insert data into the temporary // node and point it's next to NULL temp->data = num; temp->next = NULL;.

// Check if head is null, create a // linked list with temp as head // and tail of the list if (head == NULL) // Else insert the temporary node // after the tail of the existing // node and make the temporary node // as the tail of the linked list else tail = tail->next; } }.

// Return the list return head; } // Function to concatenate the two lists node* mergelists (node** head1, node** head2) tail = tail->next; }.

// return the concatenated lists as a // single list - head1 return *head1; } // Sort the linked list using bubble sort void sortlist (node** head1).

temp = temp->next; } curr = curr ->next; } } // Driver Code int main() { node* head1 = new node; node* head2 = new node; head1 = NULL; head2 = NULL; // Given Linked List 1 head1 = getData (head1, 4); head1 = getData (head1, 7); head1 = getData (head1, 5); // Given Linked List 2 head2 = getData (head2, 2); head2 = getData (head2, 1); head2 = getData (head2, 8); head2 = getData (head2, 1);.

// Merge the two lists // in a single list head1 = mergelists (&head1, &head2); // Sort the unsorted merged list sortlist (&head1); // Print the final // sorted merged list setData (head1); return 0; }.

output.