注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2014.12.13 [转] No. 29 - Loop in List  

2014-12-13 16:08:30|  分类: 技术博客 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
link
Question 1: How to check whether there is a loop in a linked list? For example, the list in Figure 1 has a loop.
2014.12.13 No. 29 - Loop in List - tassardge - 火车的家
 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 Kth 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.
2014.12.13 No. 29 - Loop in List - tassardge - 火车的家
  
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. 
  评论这张
 
阅读(255)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017