Interview Coding: Reversing a Singly Linked List in C

Here's a classic interview whiteboard exercise: reversing a singly linked list.  This was extremely popular in the 1980s and 1990s, because C/C++ were the most popular languages at that time.  You had to have a basic knowledge of pointers, linked lists, allocating/deallocating memory, etc, and you could guarantee that this question would be asked.  But as we've moved into languages liked Java and C#, which provide advanced functionality to manage the heap with garbage collection, and especially with C#'s use of generic collections in .NET Framework 2.0, most of us have pleasantly forgotten about the drudge work in managing linked lists.  But it's still a valid interview question, though when you are asked, it's like getting hit with an arctic blast of wind.

I will present a solution in C, perhaps not the perfect one, as there are many approaches.

First of all, let's define a Node structure that is the building block of the linked list:

// Node structure representing a single item in the list.
struct node
{
    node(char val) {a = val;}
    char a;
    node* next;
};

This is a very simple Node structure, it contains a single char, and a pointer to the next node in the linked list.  The constructor takes a char value so we can construct the object and set the value at the same time.  You want to keep this simple during the interview. 

Let's create a linked list, three nodes, with the values ABC.  It won't be necessary for you to write this code during the interview, but just in case you were born after 1980 and never saw a linked list constructed before, here it is:

    // Test revlist with a list of 4 items, abcd.
    node* head = NULL;
    node* node1 = new node('a');
    head = node1;
    node* node2 = new node('b');
    node1->next = node2;
    node* node3 = new node('c');
    node2->next = node3;
    node3->next = NULL;

Now let's write the function that reverses this list.  There are a few ways to do it.  One way is to loop through the list, create a temporary node pointer, and swap node pairs until you get to the end. 

// Reverse a singly linked list.
// Take the head of the list and return the new head of
// the reversed list.
node* revlist_simple(node* head)
{
  // init the return value (new head) to null
  node *ret = NULL;
  // walk thru the existing list.
  // let's say it's a -> b -> c
  while (head != NULL) 
  {
    // tmp = a, b, c
    node *tmp = head;
    // head = b, c, null
    head = head->next;
    // a->next = null
    // b->next = a
    // c->next b
    tmp->next = ret;
    // ret = a
    // ret =b
    // c
    ret = tmp;
  }
  // now the list is:
  // c-> b -> a -> null
   // return the head of the reverse linked list.
  return ret;
}

As I said at the beginning of this article, this isn't the only way to reverse a linked list.  There are many other approaches that are probably more efficient.

Thank you to the commenter who suggested this much simpler approach, rather than the first clunky way I tried to do it.