Week 9: Exercises

1. Append to List

Write a procedure that appends a value to a linked list.

2. Delete First

Write a procedure that deletes the first node (if any) in a linked list.

3. Delete Last

Write a procedure that deletes the last node (if any) in a linked list.

4. Destroying a List

Write a procedure that takes a pointer to a linked list and calls dispose to destroy every node in the list.

5. Recursive Read

Write a recursive function that reads integers from standard input until EOF and returns a linked list containing all of them.

6. Rotate a List

Write a procedure that moves the last node in a linked list to the head of the list.

7. Second To Last

Write a function that returns the second-to-last element of a linked list of non-negative integers. If there is no such element, return -1.

8. Delete the Nth

Write a procedure that deletes the Nth element (if any) of a linked list.

9. Delete Every Other

Write a procedure that deletes every other element of a linked list, starting with the first.

10. Reverse a List

Write a function or procedure that reverses a linked list. Do not allocate any additional memory.

11. Smoothing a List

Write a procedure that “smooths” a linked list of reals by averaging each value with the following value (if any) and preceding value (if any).

12. Even/Odd Split

Write a function that splits a linked list into two lists, one containing even numbers, one odd. The numbers in each list should appear in the same order as in the original list.

13. Cycle

Write a function that takes an array of integer representing a permutation of the integers 0, …, N – 1, where N is the length of the array. The function should return true if the permutation is a single cycle.