## Linked List Exercises

### May 4, 2018

I like to do exercises on linked lists. In languages like C, linked lists provide good drill for students who are uncertain about structures and pointers; in any language, lists provide good drill on recursion. Today’s exercise is about linked lists; we’ve seen some of these before, but it’s good to review:

- Take a list of integers and rearrange it so all the even integers appear before all the odd integers, with both evens and odds appearing in the output in the same order as the input.
- Take a list of integers, split it into two lists each containing alternate elements from the input list, then join the two lists back together.
- Take a list of integers and rearrange it so alternate nodes are each greater than their two adjacent nodes; in other words, the integers are in alternating high-low order.

Your task is to perform the three linked list exercises described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

task1b is still making two passes. The 2nd pass spans the (reverse evens) and (reverse odds). (And task1a and task1b both have a third partial pass with that append, as it re-scans the even part of the list again).

Here’s a version that truly makes one pass, assuming that the provided list may be mutated in place:

I agree, though, that task1a is the easiest to read.

A Haskell solution. Note that altHighLow satisfies the requirements of problem 3, even though its output differs from that of @programmingpraxis’ solution. I interpret “the integers are in alternating high-low order” as meaning the first element should always be a “high” element.

[…] worked on linked lists in the previous exercise, so today we will work on […]

[…] Linked List Exercises […]

Here’s a solution in C. For tasks 1 and 2, it uses O(1) space and O(n) time. For task 3, it uses O(1) space and O(n log n) time, using a linked-list version of merge sort that doesn’t have the O(n) storage requirement of the array variant, and doesn’t use recursion (thus no added space from recursive calls).

Examples: