**computer science - C++ ****Lesson
34: Linked-List Practice**

**INTRODUCTION:**
In Lesson 22, you developed a recursive merge sort algorithm using
arrays. An unordered linked list is
difficult to sort given its sequential nature, but a recursive merge sort can be
developed for linked lists. The
algorithms required (split and merge) will provide excellent practice in working
with linked lists. After applying a
recursive merge sort to a linked list, another function to reverse the list will
be written.

The key topics for this lesson are: A.
Merge Sort with Linked Lists B.
A Reverse List Algorithm

**DISCUSSION:**
A. __Merge Sort with Linked Lists__

1. A linked list can be sorted using a recursive merge sort algorithm. Here are the steps:

a. Split the list into two smaller lists.

b. Recursively sort these two lists using merge sort.

c. Merge the two sorted lists together.

2. Suppose we begin with a list of seven nodes, pointed to by A.

3. We then split this list into two smaller lists which differ in size by no more than one node. It does not matter which values end up in either list. In the example to follow, list A will take the first half of the list while list B will have the second half of the original list.

4. Next, we recursively sort these two lists.

5. Finally, we merge these two sorted lists together.

6. The lab exercise gives you more specific instructions about implementing this merge sort concept with linked lists.

B. __A
Reverse List Algorithm__

1. Suppose
we take the sorted list from section A.5. above and reverse the order.
The resulting list now looks like this:

2. In
the lab exercise you will develop a function to reverse the order of the nodes
in a linked list. Your algorithm
should __not__ create a duplicate list which is reversed in order. The algorithm should manipulate the nodes of the one list as
necessary to produce the reversed list.

**SUMMARY/REVIEW:**
You are encouraged to look over your code for functions *merge*
and *mergesort* from Lesson 22.
Reviewing these algorithms as applied to arrays will help you to solve
the same mergesort concept with linked lists.

**ASSIGNMENT:**
Lab Exercise L.A.34.1, *MergeList*