EC Lecture Notes - Lecture 15: Linked List

• School: National Institute of Technology - NIT Manipur
• Department: Communications
• Course: EC

Document Summary

Sort a linked list in o(n log n) time using constant space complexity. Input : 1 -> 5 -> 4 -> 3. Returned list : 1 -> 3 -> 4 -> 5. //function to insert in list void insert(int x,node **head) { if(*head == null){ *head = new node; (*head)->data = x; (*head)->next = null; return; Node *temp = new node; temp->data = (*head)->data; temp->next = (*head)->next; (*head)->data=x; (*head)->next=temp; //function to print the list void print(node *head) { Node *temp=head; while(temp!=null) { cout<data<next; //merged is equal to temp so in the end we have the top node. merged = temp; sort list1. //while either firstnode or secondnode becomes null while(firstnode != null && secondnode != null) { if(firstnode->data<=secondnode->data) { temp->next = firstnode; firstnode = firstnode->next; else { temp->next = secondnode; secondnode = secondnode->next; temp = temp->next;