[原]Reverse A Linked List

Recursion is great to resolve many problems including reverse of a linked list. First let's check the non-recursive version of reverse.

To reverse a linked list, we start from the head (in this essay we will use linked list without extra head node). One way is to use a stack, pushes all nodes started from head to the last one. Then pops all nodes and appends them to the reversed list. The way is simple but not straightforward. And it's not simple enough and occupies extra space. If the size of list is very large, the space efficiency is poor. Also the time consumed contains 1. traverse the whole list to push all nodes into stack, and 2. traverse the whole stack (which is the whole list, again) and construct the new list.

So we consider another way. Here we don't need any extra spaces and only need to traverse the list once. It can be demonstrated as following:

　｜ｐｒｅｖ　　｜ｃｕｒ　　｜ｎｅｘｔ
　ｖ　　　　　　ｖ　　　　　ｖ
　　　　　　　－－－　　　－－－　　　－－－　　　　　　　　　－－－
ＮＵＬＬ　　　｜　｜－－＞｜　｜－－＞｜　｜－－＞．．．－－＞｜　｜－－＞ＮＵＬＬ
　　　　　　　－－－　　　－－－　　　－－－　　　　　　　　　－－－

　　　　　　　　　　　　　　　　　　　　Ｉ

　　　　　　　　　　　　　　３　　　　　５
　　　　　　　２｜ｐｒｅｖ　｜ｃｕｒ　　｜ｎｅｘｔ
　　　　　　　　ｖ　　　　　ｖ　　　　　ｖ
　　　　　　　－－－　　　－－－　　　－－－　　　　　　　　　－－－
ＮＵＬＬ＜－－｜　｜＜－－｜　｜　　　｜　｜－－＞．．．－－＞｜　｜－－＞ＮＵＬＬ
　　　　　１　－－－　４　－－－　　　－－－　　　　　　　　　－－－

　　　　　　　　　　　　　　　　　　　　ＩＩ
OK, let's check the code.

The definition of node:

struct LinkedList
{
    int v;
    LinkedList* n;
};

Auxiliary function to append a node to the list and can be used to construct a new list:

LinkedList* Append(LinkedList* aList, LinkedList* aNode)
{
    if (!aList) return aNode;
    LinkedList* temp = aList;
    while (temp->n) temp = temp->n;
    temp->n = aNode;
    aNode->n = NULL;
    return aList;
}

Other functions such as insert a node are not listed here because they are not used.

As illustrate in the diagram above, 5 steps need to reverse 2 nodes:

LinkedList* Rev(LinkedList* aList)
{
    if (!aList) return NULL;
    LinkedList* prev = NULL;
    LinkedList* cur = aList;
    LinkedList* next = aList->n;
    while (next)
    {
        cur->n = prev;
        prev = cur;
        cur = next;
        next = next->n;
        cur->n = prev;
    }
    return cur;
}

Now we consider the recursive way:

if next node not null
    then reverse the list starts from next node and save the reversed list;
else
    append the node to the reversed list started from next node and return the whole list;

It's easy to implement the reverse:

LinkedList* RevRecur(LinkedList* aList)
{
    if (!aList) return NULL;
    if (aList->n)
        aList->n = RevRecur(aList->n);
    return Append(aList->n, aList);
}