computer science - C++ Lesson 34: Linked-List Practice
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
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
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