If there isn't tail recursion should I implement it with trampolining in the compiler first?

put it in a stack then take it back out, first in last out.

Follow up is usually: now do that with O(1) memory.

This doesn't seem like a very valuable interview question anymore because it's well known and you can probably google the simple answer, but if not this is the basic idea (walk the list once pointing each next at the previous node and return the new head when you reach the end):

  List *Reverse( List *pList )
  {
	List *pPrevious = nullptr;
	List *pCurrent = pList;
	while ( pCurrent )
	{
		List *pNext = pCurrent->GetNext();
		pCurrent->SetNext( pPrevious );
		pPrevious = pCurrent;
		pCurrent = pNext;
	}
	return pPrevious;
  }

I've never seen an interview question that I couldn't Google an answer for, after the fact. That doesn't seem like a necessary criterion to decide if it's a valuable question or not. However, it's a problem if the question's so common that even unqualified candidates would be able to answer it.

We ask these questions for a few reasons. You hope that the candidate hasn't seen it before, because you want to see their problem-solving process. You also want to see which questions they ask, which assumptions they make, etc. How well do they explain their thought process? Do they understand the algorithm, or did they rote-learn it?

Will they need to jump through algorithmic hoops writing a CRUD app? Probably not...but they'll need to solve problems creatively. It might be better to walk through an actual investigation+bugfix in a piece of software, but that takes more time to do (interviewer+candidate) and more effort (interviewer) to set up, so it's not surprising that most interviewers would take the easier way out.

I used these examples for interviews back in the 90s. I liked the follow ups. I don't use it any more because linked lists with pointers doesn't seem relevant now that computer languages have some sort of native dynamic list implementation.

GAAAAAAHHHH!! I mean, Of course I knew that already :)

It's hard to know you can simulate a function stack with a for loop I guess...