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.
Programming Praxis 
;; Obviously, I'm in those exercises to show off the advantages of ;; Common Lisp. The downside is that it usually defeats the purpose ;; of the exercise :-) Those are typical. (defun even-before-odd (loi) "Return a list of the integers in LOI, rearranged 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." (stable-sort (copy-list loi) (lambda (a b) (when (evenp a) (oddp b))))) (defun test/even-before-odd () (assert (equal (even-before-odd '()) '())) (assert (equal (even-before-odd '(1)) '(1))) (assert (equal (even-before-odd '(1 3 1 3 5 7 5 7 1 3 1 3)) '(1 3 1 3 5 7 5 7 1 3 1 3))) (assert (equal (even-before-odd '(2 4 2 4 6 8 6 8 2 4 2 4)) '(2 4 2 4 6 8 6 8 2 4 2 4))) (assert (equal (even-before-odd '(1 3 1 3 5 7 2 4 2 4 6 8)) '(2 4 2 4 6 8 1 3 1 3 5 7))) (assert (equal (even-before-odd '(1 2 3 4 5 6 7 8 9)) '(2 4 6 8 1 3 5 7 9))) :success) (defun reorder-alternating-elements (list) "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." (loop :with left := nil :for element :in list :if (setf left (not left)) :collect element :into left-part :else :collect element :into right-part :finally (return (nconc left-part right-part)))) (defun test/reorder-alternating-elements () (assert (equal (reorder-alternating-elements '()) '())) (assert (equal (reorder-alternating-elements '(a)) '(a))) (assert (equal (reorder-alternating-elements '(a 1)) '(a 1))) (assert (equal (reorder-alternating-elements '(a 1 b 2 c 3 d 4)) '(a b c d 1 2 3 4))) :success) (defun zip (a b) (if a (if b (list* (car a) (car b) (zip (cdr a) (cdr b))) a) b)) (defun test/zip () (assert (equal (zip '() '()) '())) (assert (equal (zip '(a) '()) '(a))) (assert (equal (zip '() '(1)) '(1))) (assert (equal (zip '(a b) '()) '(a b))) (assert (equal (zip '() '(1 2)) '(1 2))) (assert (equal (zip '(a) '(1)) '(a 1))) (assert (equal (zip '(a b c) '(1 2 3)) '(a 1 b 2 c 3))) (assert (equal (zip '(a b c) '(1 2 3 4 5)) '(a 1 b 2 c 3 4 5))) (assert (equal (zip '(a b c d e) '(1 2 3)) '(a 1 b 2 c 3 d e))) :success) (defun alternate-high-low (lor) "Return a list of reals rearranged so alternate elements are each greater than their two adjacent elements; in other words, the reals are in alternating high-low order." ;; This implementation is O(nlogn) but walks the elements 6 more times! ;; But it has two advantages: ;; 1- it's correct, ;; 2- it's implemented quickly, ;; so you can start using it, and have time to develop and debug a more ;; optimized implementation (if needed). (let* ((sorted (sort (copy-list lor) (function <))) (length (length sorted))) (zip (subseq sorted 0 (ceiling length 2)) (reverse (subseq sorted (ceiling length 2)))))) (defun test/alternate-high-low () (flet ((alternatep (list) (or (null (cddr list)) (loop :while (cddr list) :always (and (<= (first list) (second list)) (>= (second list) (third list))) :do (setf list (cddr list))) (loop :while (cddr list) :always (and (>= (first list) (second list)) (<= (second list) (third list))) :do (setf list (cddr list)))))) (assert (alternatep (alternate-high-low '()))) (assert (alternatep (alternate-high-low '(1)))) (assert (alternatep (alternate-high-low '(1 2)))) (assert (alternatep (alternate-high-low '(1 2 3)))) (assert (alternatep (alternate-high-low '(1 2 3 4 5 6 7 8 9))))) :success) ;; slow fast reversed result ;; (1 2 3 4 5 6 7 8) (1 2 3 4 5 6 7 8) ;; (2 3 4 5 6 7 8) (3 4 5 6 7 8) (1) ;; (3 4 5 6 7 8) (5 6 7 8) (2 1) ;; (4 5 6 7 8) (7 8) (3 2 1) ;; (5 6 7 8) () (4 3 2 1) ;; (6 7 8) () (3 2 1) (4 5) ;; (7 8) () (2 1) (3 6 4 5) ;; (8) () (1) (2 7 3 6 4 5) ;; () () () (1 8 2 7 3 6 4 5) ;; slow fast reversed result ;; (1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 8 9) ;; (2 3 4 5 6 7 8 9) (3 4 5 6 7 8 9) (1) ;; (3 4 5 6 7 8 9) (5 6 7 8 9) (2 1) ;; (4 5 6 7 8 9) (7 8 9) (3 2 1) ;; (5 6 7 8 9) (9) (4 3 2 1) ;; (6 7 8 9) (9) (3 2 1) (4 5) ;; (7 8 9) (9) (2 1) (3 6 4 5) ;; (8 9) (9) (1) (2 7 3 6 4 5) ;; (9) (9) () (1 8 2 7 3 6 4 5) ;; () (9) () (9 1 8 2 7 3 6 4 5) (defun alternate-high-low (lor) "Return a list of reals rearranged so alternate elements are each greater than their two adjacent elements; in other words, the reals are in alternating high-low order." ;; This implementation is O(nlogn) but walks the elements only 1 more time, ;; but it needs O(n/2) storage (reverse stack). ;; Since it's tail recursive, it could be tail call optimized, but since ;; this is not mandatory that a CL implementation performs TCO, we'll ;; rewrite it in iteration form. (if (cddr lor) (labels ((reoder (slow fast reversed result) (cond ((cdr fast) (reoder (cdr slow) (cddr fast) (cons (car slow) reversed) result)) (slow (if reversed (reoder (cdr slow) fast (cdr reversed) (list* (car reversed) (car slow) result)) (cons (car slow) result))) (fast (list* (car fast) result)) (t result)))) (let ((sorted (sort (copy-list lor) (function <)))) (reoder sorted sorted '() '()))) lor)) (defun alternate-high-low (lor) "Return a list of reals rearranged so alternate elements are each greater than their two adjacent elements; in other words, the reals are in alternating high-low order." ;; This implementation is O(nlogn) but walks the elements only 1 more time, ;; but it needs O(n/2) storage (reverse stack). (if (cddr lor) (let ((sorted (sort (copy-list lor) (function <)))) (loop :with slow := sorted :with fast := sorted :with reversed := '() :with result := '() :do (cond ((cdr fast) (setf reversed (cons (car slow) reversed) slow (cdr slow) fast (cddr fast))) (slow (if reversed (setf result (list* (car reversed) (car slow) result) slow (cdr slow) reversed (cdr reversed)) (return (cons (car slow) result)))) (fast (return (list* (car fast) result))) (t (return result))))) lor)) (progn (test/even-before-odd) (test/reorder-alternating-elements) (test/zip) (test/alternate-high-low))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:
(define (task1c xs) (let loop ((xs xs) (ehead #f) (etail #f) (ohead #f) (otail #f)) (cond ((null? xs) (when (and etail ohead) (set-cdr! etail ohead)) (when otail (set-cdr! otail '())) (or ehead ohead '())) ((even? (car xs)) (when etail (set-cdr! etail xs)) (loop (cdr xs) (or ehead xs) xs ohead otail)) (else (when otail (set-cdr! otail xs)) (loop (cdr xs) ehead etail (or ohead xs) xs)))))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.
import Data.List (partition, sortOn) import Data.Ord (Down(..)) -- Problem 1 -- -- Re-order the argument so that all its even elements appear before the odd -- elements. Otherwise, maintain the relative order of the elements. evensThenOdds :: Integral a => [a] -> [a] evensThenOdds = uncurry (++) . partition even -- Problem 2 -- -- Partition the argument into a pair of lists containing alternating elements, -- returning the concatenation of the two lists. altJoin :: [a] -> [a] altJoin = uncurry (++) . foldr (\x (l, r) -> (x:r, l)) ([], []) -- Problem 3 -- -- Re-order the argument to alternate between larger and smaller elements, -- always starting the result with the largest element. altHighLow :: Ord a => [a] -> [a] altHighLow xs = let xs' = sortOn Down xs in uncurry merge $ splitAt ((length xs' + 1) `div` 2) xs' -- Merge two lists, alternating between elements of the first, then second, -- lists. merge :: [a] -> [a] -> [a] merge (x:xs) (y:ys) = x : y : merge xs ys merge xs [] = xs merge [] ys = ys main :: IO () main = do print $ evensThenOdds [1, 8, 3, 6, 5, 4, 7, 2, 9] print $ evensThenOdds [1..9] print $ altJoin [1..9] print $ altHighLow [1..9] print $ altHighLow [1..8][…] 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).
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node* next; } node_t; node_t* argv_to_list(int argc, char* argv[]) { node_t* list = NULL; for (size_t i = argc - 1; i >= 1; --i) { node_t* node = (node_t*)malloc(sizeof(node_t)); node->value = atoi(argv[i]); node->next = list; list = node; } return list; } void print_list(node_t* list) { bool head = true; printf("{"); while (list != NULL) { if (!head) printf("->"); printf("%d", list->value); list = list->next; head = false; } printf("}"); printf("\n"); } void free_list(node_t* list) { while (list != NULL) { node_t* next = list->next; free(list); list = next; } } void task1(node_t** list) { node_t* even_head = NULL; node_t* even_tail = NULL; node_t* odd_head = NULL; node_t* odd_tail = NULL; node_t* node = *list; while (node) { if (node->value % 2) { if (!odd_head) { odd_head = node; odd_tail = node; } else { odd_tail->next = node; odd_tail = node; } } else { if (!even_head) { even_head = node; even_tail = node; } else { even_tail->next = node; even_tail = node; } } node_t* next = node->next; node->next = NULL; node = next; } if (!even_head) { *list = odd_head; } else { even_tail->next = odd_head; *list = even_head; } } void task2(node_t** list) { node_t* even_idx_head = NULL; node_t* even_idx_tail = NULL; node_t* odd_idx_head = NULL; node_t* odd_idx_tail = NULL; node_t* node = *list; size_t i = 0; while (node) { if (i % 2) { if (!odd_idx_head) { odd_idx_head = node; odd_idx_tail = node; } else { odd_idx_tail->next = node; odd_idx_tail = node; } } else { if (!even_idx_head) { even_idx_head = node; even_idx_tail = node; } else { even_idx_tail->next = node; even_idx_tail = node; } } node_t* next = node->next; node->next = NULL; node = next; ++i; } if (even_idx_tail) { even_idx_tail->next = odd_idx_head; } *list = even_idx_head; } // merge sort void sort(node_t** list) { size_t k = 1; while (1) { node_t* p = *list; size_t n_merges = 0; node_t* merged = NULL; node_t* tail = NULL; while (1) { if (p == NULL) break; ++n_merges; node_t* q = p; size_t psize = 0; size_t qsize = k; while (q != NULL && psize < k) { q = q->next; ++psize; } while (1) { node_t* e = NULL; bool p_avail = psize > 0; bool q_avail = qsize > 0 && q != NULL; enum next_choice {P, Q, NONE}; enum next_choice next = NONE; if (p_avail && q_avail) { if (p->value <= q->value) { next = P; } else { next = Q; } } else if (p_avail) { next = P; } else if (q_avail) { next = Q; } switch(next) { case P: e = p; p = p->next; --psize; break; case Q: e = q; q = q->next; --qsize; break; default: break; } if (e == NULL) { if (tail != NULL) tail->next = NULL; p = q; break; } if (merged == NULL) { merged = e; } else { tail->next = e; } tail = e; } } *list = merged; if (n_merges <= 1) break; k *= 2; } } size_t length(node_t* list) { size_t n = 0; while (list != NULL) { ++n; list = list->next; } return n; } void task3(node_t** list) { sort(list); size_t n = length(*list); node_t* node1 = *list; for (size_t i = 0; i < n / 2; ++i) { node1 = node1->next; } node_t* node2 = *list; *list = node1; node_t* new_head = node1; while (node1 != NULL && node2 != new_head) { node_t* node1_next = node1->next; node_t* node2_next = node2->next; node1->next = node2; node2->next = node1_next; node1 = node1_next; node2 = node2_next; } } int main(int argc, char* argv[]) { node_t* list = argv_to_list(argc, argv); printf("list:\n "); print_list(list); // Task 1 task1(&list); printf("task1(list):\n "); print_list(list); free_list(list); // Task 2 list = argv_to_list(argc, argv); task2(&list); printf("task2(list):\n "); print_list(list); free_list(list); // Task 3 list = argv_to_list(argc, argv); task3(&list); printf("task3(list):\n "); print_list(list); free_list(list); return EXIT_SUCCESS; }Examples:
$ ./linked_lists {1..9} list: {1->2->3->4->5->6->7->8->9} task1(list): {2->4->6->8->1->3->5->7->9} task2(list): {1->3->5->7->9->2->4->6->8} task3(list): {5->1->6->2->7->3->8->4->9} $ ./linked_lists {9..1} list: {9->8->7->6->5->4->3->2->1} task1(list): {8->6->4->2->9->7->5->3->1} task2(list): {9->7->5->3->1->8->6->4->2} task3(list): {5->1->6->2->7->3->8->4->9} $ ./linked_lists {1..8} list: {1->2->3->4->5->6->7->8} task1(list): {2->4->6->8->1->3->5->7} task2(list): {1->3->5->7->2->4->6->8} task3(list): {5->1->6->2->7->3->8->4} $ ./linked_lists {8..1} list: {8->7->6->5->4->3->2->1} task1(list): {8->6->4->2->7->5->3->1} task2(list): {8->6->4->2->7->5->3->1} task3(list): {5->1->6->2->7->3->8->4}