Reversing a Doubly Linked List In Place

Reversing a Doubly Linked List In Place

It actually only took me about ten minutes to sketch out--without the pressure of interviewers looking down my neck, and expecting an instant answer--and another ten minutes of actually typing in the code to create the linked list, traverse the list, and do the reverse. And once the compiler reminded me of the messy details of how to set up the struct and typedef statements for the linked list structure, it required no debugging.

#include <stdio.h>

#include <malloc.h>

struct dblLink
{
struct dblLink* prev;
struct dblLink* next;
char* data;
};

typedef struct dblLink tNode;

/* Assumes that we have a linked list and we are adding to the end. */
tNode* addNode (tNode* whereToAdd, char* data)
{
tNode* newNode;

if (whereToAdd->next == NULL)
{
/* Add another element. */
newNode = (tNode*)malloc(sizeof(tNode));
if (newNode)
{
newNode->next = NULL;
newNode->prev = whereToAdd;
newNode->data = data;
whereToAdd->next = newNode;
}
}
return (newNode);
}

int main (int argc, char* argv[])
{
tNode* head;
tNode* lastNode;
tNode* node;
tNode* oldPrev;
tNode* oldNext;

/* Create the head. */
head = (tNode*)malloc(sizeof(tNode));
if (head)
{
head->prev = NULL;
head->next = NULL;
head->data = "George Washington";
/* Now add some more entries. */
lastNode = addNode(head, "John Adams");
lastNode = addNode(lastNode, "Thomas Jefferson");
lastNode = addNode(lastNode, "James Madison");
lastNode = addNode(lastNode, "James Monroe");
printf("From head to tail.\n");
/* Print the doubly linked list. */
for (node = head; node; node = node->next)
printf("%s\n", node->data);
/* Reverse the list. */
/* Find the end of the list. */
for (node = head; node->next; node = node->next)
{
}
/* The end of the list will be the new head. */
head = node;
/* Now start at the end of the list, and work backward. */
do
{
oldPrev = node->prev;
oldNext = node->next;
node->prev = oldNext;
node->next = oldPrev;
node = node->next;
}
while (node);
printf("The list is reversed. From head to tail.\n");
/* Print the doubly linked list. */
for (node = head; node; node = node->next)
printf("%s\n", node->data);
}
}

You know, there might be a place for programming like you are a character in 24, trying to solve technical problems in the next ten minutes as though millions of lives are at stake, but I'm not applying for Chloe O'Brian's job.

UPDATE: The more I think about this, the more I suspect that the test question just threw me for a loop and flustered me. If they had said, "Here's what we want to you write. We'll leave the room, and come back in 10-15 minutes to see how you are doing," I probably would have passed the test. But at that point, I had not been on a job interview with complete strangers in at least ten years. You live and you learn. Now, I just need to scare up some job interviews....

I have decided that the chances of finding a job in Boise are quite slim, because I don't have five years of C# experience. (I don't have any, other than what I have learned on my own time these last couple of weeks.) At this point, I'm looking only at positions in the Western U.S., because this makes it possible for me to at least come home perhaps every other weekend. The time and cost of doing some from other parts of the U.S. suddenly makes that part-time job at Big O Tires as a tire technician start to look like the lesser of two evils.