Sunday, October 30, 2011

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.

12 comments:

  1. Another way, we may use recursion to solve it.

    ListNode* ReverseList(ListNode* cur,ListNode* prev)
    {
    ListNode* tempNode = cur;
    if(NULL == tempNode->m_pNext)
    {
    tempNode->m_pNext = prev;
    return tempNode;
    }
    else
    {
    tempNode = ReverseList(cur->m_pNext,cur);
    cur->m_pNext = prev;
    return tempNode;
    }
    }

    ReplyDelete
    Replies
    1. I solved it using recursion as well - I thought out was a rather elegant solution.

      Delete
  2. good one harry!

    i really like your explanation...there's another good page on this one that has both iterative and recursive solution to the problem:

    reverse linked list

    ReplyDelete
  3. Nice one! Also, check out these awesome youtube videos on link list: ( http://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P ). Well Explained!

    ReplyDelete
  4. Shouldn't you use pointer to pointer of header?
    ListNode* ReverseList(ListNode** pHead)

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. What makes you folks think that way ? Can't you see what is returned - a reversed list ?

      The caller passed head as an argument and that pointer remains untouched from callers perspective even after returning from the function. So the caller cannot expect to see a reversed list with the very same pointer that he passed as an argument to ReverseList [unless he re-assigned the very same pointer with the one returned from call i.e List = ReverseList(List)].

      He must use the one that's is returned from the function to see the reversed list.

      According to code in this blog, the original list itself is reversed without having done so on a copy and all that is in strict sense of reversing a list. But that fact should not delude the caller to expect a reversed list via old head (of course, unless it was re-assinged with the coutcome of ReverseList).

      Now, **phead can steer clear of such kind of confusion, if at all it occurs; however in that case, ReverseList ought to return nothing i.e.
      void ReverseList(ListNode** pHead);

      Delete
  5. No need to keep pReversedHead. It's equal to pPrev from the last iteration.

    ReplyDelete
  6. ListNode* ReverseList(ListNode* pHead)
    {
    ListNode* pNode = pHead;
    ListNode* pPrev = NULL;
    while(pNode != NULL)
    {
    ListNode* pNext = pNode->m_pNext;

    pNode->m_pNext = pPrev;

    pPrev = pNode;
    pNode = pNext;
    }

    return pPrev;
    }

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. Head need not be preserved; so one might as well do away with it. That calls for a little curtailment (going a little easier with nomenclature now) -

    ListNode* ReverseList(ListNode* List)
    {
    ListNode* Previous = NULL;
    while(List != NULL)
    {
    ListNode* Next = List->next_Node;
    List->next_Node = Previous;
    Previous = List;
    List = Next;
    }
    return Prev;
    }

    ReplyDelete