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. You could create a C++ solution to this problem, using templates, but that could take much longer.
Let's create a linked list, four nodes, with the values ABCD. 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; node* node4 = new node('d'); node3->next = node4; node4->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. That's perfectly valid, yet when I see this type of problem, I think about using recursion, which is how I tried to address it:
// Reverse a singly linked list. // Take the head of the list and return the new head of // the reversed list. node* revlist(node* head) { node* ptr = head; node* newHead = NULL; // if the list is empty, return NULL, or // if the list has only 1 item, return that item. if ((ptr == NULL) || (ptr->next == NULL)) { return ptr; } // Linked list has 2 or more items. // Are we at the end of the list? if (ptr->next->next != NULL) { // no, keep traversing the list until the end. newHead = revlist(ptr->next); } else { // the new head of the list is the last item. newHead = ptr->next; } // next item points to the previous item. ptr->next->next = ptr; // previous item is now the tail, it points to NULL. ptr->next = NULL; // return the head of the reverse linked list. return newHead; }
This is pretty straightforward. The function starts at the head of the singly linked list and returns the new head of the reversed linked list. It does not leave the original list untouched. For that, we would need to make a copy, but we're trying to keep this solution simple.
Let's examine this section by section. The first if-statement is vital:
// if the list is empty, return NULL, or // if the list has only 1 item, return that item. if ((ptr == NULL) || (ptr->next == NULL)) { return ptr; }
If the linked list has 0 items, the head ptr is NULL. We must detect this and return NULL. Alternatively, if this list has only 1 node, there's nothing to reverse. We must detect this and return back that node to the caller.
// Linked list has 2 or more items. // Are we at the end of the list? if (ptr->next->next != NULL) { // no, keep traversing the list until the end. newHead = revlist(ptr->next); }
This if-statement uses recursion to traverse the linked list all the way to the last two nodes. If the list is ABCD, the first time this function is called, it's looking at B->next and detecting if that is NULL. Since it is not, it calls revlist again, with B as the head of the list. It will be called another time, pointing to C as the head of the list.
else { // the new head of the list is the last item. newHead = ptr->next; }
When C is the head, the else clause will be executed. At this point, we are at the next to last node in the linked list. The new head of the reversed linked list will be the last node in the original list. C->next points to D. The D node will be the new head.
// next item points to the previous item. ptr->next->next = ptr; // previous item is now the tail, it points to NULL. ptr->next = NULL;
Now that we've found the head of the reverse list, it's time to start swapping nodes. The first time we execute this code ptr is really the C node. C points to D, the tail of the list. Now we swap them. D points to the previous node, C. C points to NULL, because it is now the tail. As the recursive stack unwinds, the rest of the list is reversed:
ptr == C, C -> D, swap, reversed list is D -> C
ptr == B, B -> C, swap, reversed list is D -> C -> B
ptr == A, A -> B, swap, reversed list is D -> C -> B -> A
Finally, we need to return the new head of the reversed linked list:
// return the head of the reverse linked list. return newHead;
This seems obvious, but a mistake could be made in the previous if-statement if you don't set newhead in the recursive call. Once the last node in the old linked list is found, it is returned through the recursive stack.
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.
Leave a comment