Задачи с приемных экзаменов на работу. Часть 1

Выполняя свое старое обещание - публикую последние вопросы с интервью по приему на работу пройденному мной вчера.

Естественно в переводе на русский язык.

Статьей это назвать конечно нельзя, но ответы я положу не сразу, так что думаю будет интересно.

Итак, три вопроса.

1. Написать функцию на С, которая будет получать в качестве параметра первый элемент связного списка.
Возвращать true если список заканчивается NULL и false если список заканчивается указание на один из предыдущих элементов списка. Список нельзя изменять.
В функции нельзя употреблять памяти больше чем на все элементы списка.

2.
Дано.
Код:
int * foo()
{
int X;
X=7;
Return &X;
}

void main(void)
{
int Y;
Y = *foo();
printf("%d", Y+3);
}

Какие будут результаты программы?

3. Имеется робот по сортировки камней разного цвета выложенных в линию колличеством N.
Имеются три цвета, красный синий и зеленый. Камни по цвету не отсортированы.
Есть две функции color(i) - возвращает цвет камня по индексу switch (I,j) меняет камни I & j местами.

Написать программу для робота который будет сортировать камни в последовательность: сначала все синие, потом все красные, потом все зеленые.

В программе нельзя использовать динамическую память. Размер общей использованной памяти в программе не должен зависить от числа камней N.
Вызывать функции color() и switch() нельзя более N раз.