#include #include

using namespace std;

struct ListNode { int info; ListNode* link; };

void insert(ListNode*& head, int x) { ListNode* p = new ListNode{x, NULL};

if (head == NULL || x info) { p->link = head; head = p; } else { ListNode* prev = head; ListNode* cur = head->link;

while (cur != NULL && x > cur->info) { prev = cur; cur = cur->link; }

p->link = prev->link; prev->link = p; } }

void print(ListNode* head) { ListNode* cur = head; while (cur != NULL) { cout info link; } cout

int main() { ListNode* head = NULL; ifstream inFile("testData.txt"); if (!inFile.is_open()) { cout

while (!inFile.eof()) { /ot end of file int i; inFile >> i; //read in an integer

if (!inFile.fail()) insert(head, i); //insert into the linked list else break; }

inFile.close();

cout

cout > x; insert(head, x); //insert into the linked list

cout

Your task: implement insertion sort using linked list. Main.cpp is provided as a function to insert an element into a sorted linked list. Now, extend that to insertion sort. The file data1.txt contains some random integers. Read that file and then conduct insertion sort. Problem formulation/evaluation: Input: data1.txt Output: print out the sorted linked list that is constructed from data1.txt 020125910120