No. 29 - Loop in List

Question 1: How to check whether there is a loop in a linked list? For example, the list in Figure 1 has a loop.

Figure 1: A list with a loop

 

A node in list is defined as the following structure:

struct ListNode

{

    int       m_nValue;

    ListNode* m_pNext;

};

Analysis: It is a popular interview question. Similar to the problem to get the K^th node from end is a list, it has a solution with two pointers.

Two pointers are initialized at the head of list. One pointer forwards once at each step, and the other forwards twice at each step. If the faster pointer meets the slower one again, there is a loop in the list. Otherwise there is no loop if the faster one reaches the end of list.

The sample code below is implemented according to this solution. The faster pointer is pFast, and the slower one is pSlow.

bool HasLoop(ListNode* pHead)

{

    if(pHead == NULL)

        return false;

    ListNode* pSlow = pHead->m_pNext;

    if(pSlow == NULL)

        return false;

    ListNode* pFast = pSlow->m_pNext;

    while(pFast != NULL && pSlow != NULL)

    {

        if(pFast == pSlow)

            return true;

        pSlow = pSlow->m_pNext;

        pFast = pFast->m_pNext;

        if(pFast != NULL)

            pFast = pFast->m_pNext;

    }

    return false;

}

Question 2: If there is a loop in a linked list, how to get the entry node of the loop? The entry node is the first node in the loop from head of list. For instance, the entry node of loop in the list of Figure 1 is the node with value 3.

Analysis: Inspired by the solution of the first problem, we can also solve this problem with two pointers. 

Two pointers are initialized at the head of a list. If there are n nodes in the loop, the first pointer forwards n steps firstly. And then they forward together, at same speed. When the second pointer reaches the entry node of loop, the first one travels around the loop and returns back to entry node.

Let us take the list in Figure 1 as an example. Two pointers, P1 and P2 are firstly initialized at the head node of the list (Figure 2-a). There are 4 nodes in the loop of list, so P1 moves 4 steps ahead, and reaches the node with value 5 (Figure 2-b). And then these two pointers move for 2 steps, and they meet at the node with value 3, which is the entry node of the loop.

Figure 2: Process to find the entry node of a loop in a list. (a) Pointers P1 and P2 are initialized at the head of list; (b) The point P1 moves 4 steps ahead, since there are 4 nodes in the loop; (c) P1 and P2 move for two steps, and meet each other.

The only problem is how to get the numbers in a loop. Let go back to the solution of the first question. We define two pointers, and the faster one meets the slower one if there is a loop. Actually, the meeting node should be inside the loop. Therefore, we can move forward from the meeting node and get the number of nodes in the loop when we arrive at the meeting node again.

The following function MeetingNode gets the meeting node of two pointers if there is a loop in a list, which is a minor modification of the previous HasLoop:

ListNode* MeetingNode(ListNode* pHead)

{

    if(pHead == NULL)

        return NULL;

    ListNode* pSlow = pHead->m_pNext;

    if(pSlow == NULL)

        return NULL;

    ListNode* pFast = pSlow->m_pNext;

    while(pFast != NULL && pSlow != NULL)

    {

        if(pFast == pSlow)

            return pFast;

        pSlow = pSlow->m_pNext;

        pFast = pFast->m_pNext;

        if(pFast != NULL)

            pFast = pFast->m_pNext;

    }

    return NULL;

}

We can get the number of nodes in a loop of a list, and the entry node of loop after we know the meeting node, as shown below:

ListNode* EntryNodeOfLoop(ListNode* pHead)

{

    ListNode* meetingNode = MeetingNode(pHead);

    if(meetingNode == NULL)

        return NULL;

    // get the number of nodes in loop

    int nodesInLoop = 1;

    ListNode* pNode1 = meetingNode;

    while(pNode1->m_pNext != meetingNode)

    {

        pNode1 = pNode1->m_pNext;

        ++nodesInLoop;

    }

    // move pNode1

    pNode1 = pHead;

    for(int i = 0; i < nodesInLoop; ++i)

        pNode1 = pNode1->m_pNext;

    // move pNode1 and pNode2

    ListNode* pNode2 = pHead;

    while(pNode1 != pNode2)

    {

        pNode1 = pNode1->m_pNext;

        pNode2 = pNode2->m_pNext;

    }

    return pNode1;

}

The discussion about these two problems 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.

No. 01 - Binary Search Tree and Double-linked List

Question: Convert a binary search tree to a sorted double-linked list. We can only change the target of pointers, but cannot create any new nodes.

For example, if we input a binary search tree as shown on the left side of the Figure 1, the output double-linked list is shown on the right side.

Figure 1: The conversion between a binary search tree and a sorted double-linked list

A node of binary search tree is defined in C/C++ is as:

struct BinaryTreeNode

{

    int                    m_nValue;

    BinaryTreeNode*        m_pLeft; 

    BinaryTreeNode*        m_pRight;

};

Analysis: In a binary tree, each node has two pointers to its children. In a double-linked list, each node also has two pointers, one pointing to the previous node and the other pointing to the next one. Additionally, binary search tree is a sorted data structure. In a binary search tree, value in parent is always greater than value of its left child and less than value of its right child. Therefore, we can adjust a pointer to its left child in binary search tree to its previous node in a double-linked list, and adjust a pointer to its right child to its next node. 

It is required that the converted list should be sorted, so we can adopt in-order traversal. That is because according to the definition of in-order traversal we traverse from nodes with less value to nodes with greater value. When we reach the root of the binary tree in Figure1, the tree may be viewed as three parts: a root with value 10, a left sub-tree with root value 6 and a right sub-tree with root value 14. According to the definition of sorted double-linked list, the root node with value 10 should be linked to the node with the greatest value (the node with value 8) in its left sub-tree, and it should be also linked to the node with the least value (the node with value 12) in its right sub-tree, as shown in Figure 2.

Figure 2: A tree with three parts: root, left sub-tree, right sub-tree. After we can the left sub-tree and right sub-tree, and we link them with the root, and then we can get a sorted double-linked list

According to the definition of in-order traversal, the sub-tree should be already converted to a sorted list when we reach its root (the node with value 10), and the last node in the sorted list should be the node with the greatest node (the node with value 8). If we link the last node in list to the root node of tree, then the root is the last node in list now. We continue to convert its right sub-tree, and connect the root to the node with its least value. How to convert its left sub-tree and right sub-tree? It should be similar to converting the whole tree. Therefore, we can solve it with recursion.

We can write the following code based on the recursive solution:

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)

{

    BinaryTreeNode *pLastNodeInList = NULL;

    ConvertNode(pRootOfTree, &pLastNodeInList);

    // pLastNodeInList points to the tail of double-linked list,

    // but we need to return its head

    BinaryTreeNode *pHeadOfList = pLastNodeInList;

    while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)

        pHeadOfList = pHeadOfList->m_pLeft;

    return pHeadOfList;

}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)

{

    if(pNode == NULL)

        return;

    BinaryTreeNode *pCurrent = pNode;

    if (pCurrent->m_pLeft != NULL)

        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

    pCurrent->m_pLeft = *pLastNodeInList;

    if(*pLastNodeInList != NULL)

        (*pLastNodeInList)->m_pRight = pCurrent;

    *pLastNodeInList = pCurrent;

    if (pCurrent->m_pRight != NULL)

        ConvertNode(pCurrent->m_pRight, pLastNodeInList);

}

In the code above, pLastNodeInList is the last node (also the node with the greatest value) in the converted double-linked list. When we reach the value with 10, its left sub-tree has already been converted, and pLastNodeInList points to the node with 8. Afterwards we connect the root node to the linked list, and the node with 10 becomes the last node in the list (new node with the greatest value), so we move the pointer pLastNodeInList to the node with 10. We continue to invoke the function recursively with parameter pLastNodeInList to convert the right sub-tree. After we reach the left most node in the right sub-tree (also the node with least value), we linked it to the node with 10 in the list.

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.