Thursday, April 26, 2012

Reversing a linked list in C++

Linked list is one of the most popular data structures in Computer Science. Read more about linked lists [here]. In this entry we will write a function to reverse a linked list in C++ efficiently.
Link* reverse_list(Link* p)
{
    if (p == NULL)
    {
        return NULL;
    }

    Link* h = p;
    p = p->next;
    h->next = NULL;

    while(p != NULL)
    {
        Link* t = p->next;
        p->next = h;
        h = p;
        p = t;
    }

    return h;
}
Enjoy.

No comments: