C++ Program: find the middle node in the linked list. Input: put the giving integers list below in a text file.

a list of integers

91 322 9 10 77 8 999 12 133 14 8 538 29 91 88 702 361 637 99

using insertion sort the task is to construct an ordered linked list (in ascending order), then, use the step below to code.(step is hint how to code)

II. inFile (use argv[1]): A text file contains a list of integers

********************************

II. outFile1 (use argv[2]): a text file includes

i) The completed sorted linked list;

ii) The memory address and the data in the middle node

outFile2( use argv[3]): All debugging outputs.

********************************

III. Data structure: Must have all the object classes as given below.

********************************

- A linkedList class

- listNode class

- data (int)

- next (listNode *)

- printNode (node) // use the format:

(this node data, this nodes memo address, next nodes memo address, next nodes data)

see print list example below.

- listHead (listNode *) // Initially it points to a dummy node

- constructLL ()

- findMiddleNode ()

- listInsert ()

- findSpot () // Use the findSpot algorithm steps taught in class.

- printList (listHead, outFile)

// print the list to outFile, from listHead to the end of the list in the following format:

listHead (this node data, this nodes memo address, next nodes memo address, next nodes data) (this node data, this nodes memo address, next nodes memo address, next nodes data) . . . . . NULL

For example:

listHead ( -9999, 001010, 101100, 3) (3, 101100, 010111, 7) ( 7, 010111, 101010, 18)............ --> NULL

******************************************

IV. Main( )

******************************************

Step 1: inFile open input file using argv[1]

outFile1, outFile1 open outfiles using argv[2] and argv[3]

Step 2: listHead get a new listNode, as the dummy listNode, with (-9999, null) for listHead to point to.

Step 3: constructLL (listHead, inFile, outFile2)

Step 4: printList (listHead, outFile1) // final print the complete list

Step 5: middleNode findMiddleNode (listHead, outFile2)

Step 6: printNode (middleNode, outFile1)

Step 7: Close all files

******************************************

V. constructLL (listHead, inFile, outFile2)

******************************************

Step 1: data get from inFile

Step 2: newNode get a new listNode (data, null)

Step 3; listInsert (listHead, newNode)

Step 4: printList (listHead, outFile2) // debug prints

Step 5: repeat step 1 step 4 until the end of inFile

******************************************

V. listInsert (listHead, newNode)

******************************************

Step 1: Spot findSpot (listHead, newNode)

Step 2: newNodes next Spots next

Spots next newNode

******************************************

VI. findSpot (listHead, newNode)

******************************************

Step 1: Spot listHead

Step 2: if Spots next != null *and* Spots nexts data < newNodes data

Spot Spots next

Step 3: repeat Step 2 until condition failed

Step 4: return Spot

******************************************

VII. findMiddleNode (listHead, outFile2)

******************************************

Step 0: walk1 listHead

walk2 listHead

Step 1: printNode (walk1, outFile2)

Step 2: if walk2 != null *and* walk2s next != null

walk1 walk1s next

walk2 walk2s nexts next

Step 3: repeat step 1 to step 2 until condition failed

Step 4: return walk1