## Linked List Exercises

### May 4, 2018

For the first task, we run through the list twice, creating intermediate lists of evens and odds, then put them back together:

(define (task1a xs) (append (filter even? xs) (filter odd? xs)))

> (task1a '(1 2 3 4 5 6 7 8 9)) (2 4 6 8 1 3 5 7 9)

We could have written `task1`

to make a single pass splitting evens and odds, but that’s more work, and probably no faster in practice:

(define (task1b xs) (let loop ((xs xs) (evens (list)) (odds (list))) (cond ((null? xs) (append (reverse evens) (reverse odds))) ((even? (car xs)) (loop (cdr xs) (cons (car xs) evens) odds)) (else (loop (cdr xs) evens (cons (car xs) odds))))))

> (task1b '(1 2 3 4 5 6 7 8 9)) (2 4 6 8 1 3 5 7 9)

My preference is strongly for the first version; it is simple and clear to read, which takes precedence over any potential performance advantage, unless you have clear evidence that the two-pass approach is a critical bottlenect in your program.

For the second task, we run through the list once, collecting alternate items:

(define (task2a xs) (let loop ((xs xs) (odds (list)) (evens (list))) (cond ((null? xs) (append (reverse odds) (reverse evens))) ((null? (cdr xs)) (append (reverse (cons (car xs) odds)) (reverse evens))) (else (loop (cddr xs) (cons (car xs) odds) (cons (cadr xs) evens))))))

> (task2a '(1 2 3 4 5 6 7 8 9)) (1 3 5 7 9 2 4 6 8)

This task is much clearer using pattern matching; here we use `list-match`

from the Standard Prelude:

(define (task2b xs) (let loop ((xs xs) (odds (list)) (evens (list))) (list-match xs (() (append (reverse odds) (reverse evens))) ((a) (loop (list) (cons a odds) evens)) ((a b . xs) (loop xs (cons a odds) (cons b evens))))))

> (task2b '(1 2 3 4 5 6 7 8 9)) (1 3 5 7 9 2 4 6 8)

The third task is hardest. First we sort the input, then split it into two pieces, *los* and *his*, and finally put them back together, being careful to preserve the correct order:

(define (task3 xs) (call-with-values (lambda () (split (quotient (length xs) 2) (sort < xs))) (lambda (los his) (let loop ((his his) (los los) (xs (list))) (cond ((null? his) xs) ((null? los) (cons (car his) xs)) (else (loop (cdr his) (cdr los) (cons (car los) (cons (car his) xs)))))))))

> (task3 '(1 2 3 4 5 6 7 8 9)) (9 4 8 3 7 2 6 1 5) > (task3 '(1 2 3 4 5 6 7 8)) (4 8 3 7 2 6 1 5)

You can run the program at https://ideone.com/j53ajn.

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: