Hi! Hope you're enjoying this blog. I have a new home at www.goldsborough.me. Be sure to also check by there for new posts <3

Monday, January 6, 2014

Reversing a linked list in C++

While randomly looking at what interviews for programmers are like, I found this "Let us see your skills" question quite often, so I tried to solve it. At first I tried it on paper really quickly, emulating a real interview situation, and kind of had the right idea, just a little logic-gap in between that I eventually discovered when coding. What you're essentially doing is storing the current node, the one before and the one after in three separate pointers. Then, you set the linking pointer of the current node to point to the node before (the previous node is initialized to NULL, thus you have the last node (the first in the original list) point to NULL, which we want). Finally, you set the previous pointer to the current one and the current to the next one, after which you again get the next pointer, rinse and repeat. At first I forgot that once you set the current pointer to the last one, you have no more link to the next, thus the gap that I quickly discovered after.

The function:

Node* Rev_LL(Node* head) //this returns the new head and takes the old one
    Node* prev = NULL; //the last element of the new list will point to NULL
    Node* next; //will hold the node after

    while (head != NULL) //traverse linked list
        next = head->next_node; //store the position of the next node
        head->next_node = prev; //link the current node to the previous one
        prev = head; //set the previous node to the current
        head = next; //and the current to the next

    head = prev; //at the end prev will be at the last element; head and next at the old NULL pointer, thus we assign it to the last

    return head; //return the new first node

Pretty simple. Despite linked lists being more or less useless considering vectors exist, they do make for nice problems.

No comments :

Post a Comment