No. 18 - Reverse a Linked List

Problem: Implement a function to reverse a linked list, and return the head of the reversed list. A list node is defined as below:

struct ListNode

{

       int       m_nKey;

       ListNode* m_pNext;

};

Analysis: Lots of pointer operations are necessary to solve problems related to linked lists. Interviewers know that many candidates are prone to make mistakes on pointer operations, so they like problems of linked list to qualify candidates’ programming abilities. During interviews, we had better analyze and design carefully rather than begin to code hastily. It is much better to write robust code with comprehensive analysis than write code quickly with many errors.

Direction of pointers should be adjusted in order to reverse a linked list. We may utilize figures to analyze visually the complex steps to adjust pointers. As shown in the list in Figure 1-a, node h, i and j are three adjacent nodes. Let us assume pointers of all nodes prior to h have been reversed after some operations and all m_pNext point to their previous nodes. We are going to reverse the m_pNext pointer in node i. The status of list is shown in Figure 1-b.

Figure 1: A list is broken when we reverse m_pNext pointers. (a) A linked list. (b) A link between node i and j is broken when all m_pNext pointers of node prior to node i point to their previous nodes.

It is noticeable that m_pNext in node i points to its previous node h, the list is broken and we cannot visit the node j anymore. We should save the node j before the m_pNext pointer of node i is adjusted to prevent the list becoming broken.

When we adjust the pointer in node i, we need to access to node h since m_pNext of node i is adjusted to point to node h. Meanwhile, we also need to access to node j because it is necessary to save it otherwise the list will be broken. Therefore, three pointers should be declared in our code, which point to the current visited node, its previous node and its next node.

Lastly we should get the head node of the reversed list. Obviously head in the reversed list should be tail of the original list. Which pointer is tail? It should be a node whose m_pNext is NULL.

With comprehensive analysis above, we are ready to write code, which is shown below:

ListNode* ReverseList(ListNode* pHead)

{

    ListNode* pReversedHead = NULL;

    ListNode* pNode = pHead;

    ListNode* pPrev = NULL;

    while(pNode != NULL)

    {

        ListNode* pNext = pNode->m_pNext;

        if(pNext == NULL)

            pReversedHead = pNode;

        pNode->m_pNext = pPrev;

        pPrev = pNode;

        pNode = pNext;

    }

    return pReversedHead;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.