Linked lists are an interviewers favourite subject matter. Whilst they are pretty easy to understand, at least in principle, they do require a little bit of brain warping to get your head around what’s going on under the hood. Of the common questions about linked lists I’ve come across, this quiz tackles the most common: how to reverse a linked list.
Question: Given the following function signature, write a function to reverse a linked list?
void reverse_single_linked_list(struct node** headRef);
Answer: Ideally, something like the following…
void reverse_single_linked_list(struct node** headRef)
{
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL)
{
next = current->next; // tricky: note the next node
current->next = result; // move the node onto the result
result = current;
current = next;
}
*headRef = result;
}
Starting from the head of the list for each iteration we make the next pointer of the ‘current’ node point to the previous node, we have to keep track of the ‘next’ node so as not to lose it as well as the ‘result’, which will end up being the new head once the complete list has been reversed.
Let’s see how that works…
KEY ------------------- H : Head N : Node C : Current X : Next R : Result 0 : Null terminator Iteration 0 X ---> ? C ---> H R ---> 0 H ---> N1 ---> N2 ---> 0 Iteration 1 X ---> N1 C ---> N1 R ---> H 0 N2 ---> 0 Iteration 2 X ---> N2 C ---> N2 R ---> N1 0 <--- H 0 Iteration 3 X ---> 0 C ---> 0 R ---> N2 0 <--- H <--- N1 <--- N2
NB. Using this technique to reverse a list you can find out if a linked list is self referential in linear 0(N) time. I’ll leave it as an exercise for the reader to figure out how this works but try repeating the steps I show above but have an additional N3 node that references back to N1 and it should be pretty obvious why. Of course, there are better ways to do this.
evilrix 