链表中的入口节点详解编程语言

题目：如果一个链表中包含环，如何找到环的入口节点？例如，在下图1所示的链表中，环的入口节点是节点3。

图1 链表中环的入口节点

【解题思路】
1、确定一个链表是否包含环。
定义两个指针（即pslow和pfast），同时从链表出发，pfast每次走两步，pslow每次走一步。如果无环，那么pfast将走到链尾而没有与pslow相遇；如果有环，那么pfast将与slow相遇。

2、找到环的入口节点。
先定义两个指针（即pahead和pbehind）。假设链表中的环有n个节点，先让phead指针走n步，再让pslow与pahead同时走，当它们相遇时，相遇点就是入口节点。
如何求链表中环的节点n？
pfast与pslow的相遇节点必在环内。先定义一个指针（即listloopnode）并初始化指向环的入口节点和一个计数变量（即loopnodecount），一边listloopnode向前走，一边loopnodecount计数，当再次回到环入口节点处时，loopnodecount就可以得到环的节点数n。

【代码】
代码1：

Node *MeetingNode(pList pnode) 
{ 
    assert(pnode); 
    pNode pslow = pnode->next; 
    if (pslow == NULL) 
    { 
        return NULL; 
    } 
    pNode pfast = pslow->next; 
    while (pfast != NULL && pslow != NULL) 
    { 
        if (pfast == pslow) 
        { 
            return pfast; 
        } 
        pslow = pslow->next; 
        pfast = pfast->next; 
        if (pfast != NULL) 
        { 
            pfast = pfast->next; 
        } 
    } 
    return NULL; 
} 
 
Node* EnterNodeOfLoop(pList pnode) 
{ 
    pNode meetingnode = MeetingNode(pnode); 
    if (meetingnode == NULL) 
    { 
        return NULL; 
    } 
 
    //得到环中节点的数目 
    int loopnodecount = 1; 
    pNode pahead = meetingnode; 
    while (pahead->next != meetingnode) 
    { 
        pahead = pahead->next; 
        ++loopnodecount; 
    } 
 
    //先移动phead，次数为环中的节点数目meetingcount 
    pahead = pnode; 
    for (int i = 0; i < loopnodecount; i++) 
    { 
        pahead = pahead->next; 
    } 
 
    //再同时移动phead和pbehind 
    pNode pbehind = pnode; 
    while (pahead != pbehind) 
    { 
        pahead = pahead->next; 
        pbehind = pbehind->next; 
    } 
    return pahead; 
}

代码2：

//判断链表带环情况 
pNode CheckCircleEnterNode(pList plist) 
{ 
    pNode fast = plist; 
    pNode slow = plist; 
    while (fast && fast->next) 
    { 
        fast = fast->next->next; 
        slow = slow->next; 
        if (fast == slow)//带环 
        { 
            return fast; 
        } 
    } 
    return NULL; 
} 
 
//求环的长度 
int GetCircleLength(pNode meet) 
{ 
    pNode pnode = meet->next;//meet为相遇点 
    int count = 1; 
    while (pnode != meet) 
    { 
        pnode = pnode->next; 
        count++; 
    } 
    return count; 
} 
 
//求环的入口点 
pNode GetCycleEntryNode(pList plist, pNode meet) 
{ 
    pNode pnode = plist; 
    if ((plist == NULL) && (meet == NULL)) 
    { 
        return NULL; 
    } 
    while (pnode != meet) 
    { 
        meet = meet->next; 
        pnode pnode->next; 
    } 
    return meet; 
}

【程序】

#define _CRT_SECURE_NO_WARNINGS 1 
# include <stdio.h> 
# include <stdlib.h> 
# include <assert.h> 
typedef int DataType; 
typedef struct Node 
{ 
DataType data; 
struct Node *next; 
}Node, *pList, *pNode; 
void InitLinkList(pList *pplist) 
{ 
assert(pplist); 
*pplist = NULL; 
} 
void PushBack(pList *pplist, DataType x) 
{ 
pNode cur = *pplist; 
pNode pnode = NULL; 
assert(pplist); 
pnode = (pNode)malloc(sizeof(Node)); 
if (pnode == NULL) 
{ 
perror("PushBack::malloc"); 
exit(EXIT_FAILURE); 
} 
pnode->data = x; 
pnode->next = NULL; 
if (cur == NULL) 
{ 
*pplist = pnode; 
} 
else 
{ 
while (cur->next != NULL) 
{ 
cur = cur->next; 
} 
cur->next = pnode; 
} 
} 
void Display(pList plist) 
{ 
pNode cur = plist; 
while (cur) 
{ 
printf("%d-->", cur->data); 
cur = cur->next; 
} 
printf("over/n"); 
} 
void PrintNode(pList plist) 
{ 
pNode cur = plist; 
printf("%d/n", cur->data); 
} 
void Destroy(pList *pplist) 
{ 
pNode cur = *pplist; 
assert(pplist); 
while (cur) 
{ 
pNode del = cur; 
cur = cur->next; 
free(del); 
} 
*pplist = NULL; 
} 
Node *MeetingNode(pList pnode) 
{ 
assert(pnode); 
pNode pslow = pnode->next; 
if (pslow == NULL) 
{ 
return NULL; 
} 
pNode pfast = pslow->next; 
while (pfast != NULL && pslow != NULL) 
{ 
if (pfast == pslow) 
{ 
return pfast; 
} 
pslow = pslow->next; 
pfast = pfast->next; 
if (pfast != NULL) 
{ 
pfast = pfast->next; 
} 
} 
return NULL; 
} 
Node* EnterNodeOfLoop(pList pnode) 
{ 
pNode meetingnode = MeetingNode(pnode); 
if (meetingnode == NULL) 
{ 
return NULL; 
} 
//得到环中节点的数目 
int loopnodecount = 1; 
pNode pahead = meetingnode; 
while (pahead->next != meetingnode) 
{ 
pahead = pahead->next; 
++loopnodecount; 
} 
//先移动phead，次数为环中的节点数目meetingcount 
pahead = pnode; 
for (int i = 0; i < loopnodecount; i++) 
{ 
pahead = pahead->next; 
} 
//再同时移动phead和pbehind 
pNode pbehind = pnode; 
while (pahead != pbehind) 
{ 
pahead = pahead->next; 
pbehind = pbehind->next; 
} 
return pahead; 
} 
//方法二 
判断链表带环情况 
//pNode CheckCircleEnterNode(pList plist) 
//{
 
//  pNode fast = plist; 
//  pNode slow = plist; 
//  while (fast && fast->next) 
//  {
 
//      fast = fast->next->next; 
//      slow = slow->next; 
//      if (fast == slow)//带环 
//      {
 
//          return fast; 
//      } 
//  } 
//  return NULL; 
//} 
// 
求环的长度 
//int GetCircleLength(pNode meet) 
//{
 
//  pNode pnode = meet->next;//meet为相遇点 
//  int count = 1; 
//  while (pnode != meet) 
//  {
 
//      pnode = pnode->next; 
//      count++; 
//  } 
//  return count; 
//} 
// 
求环的入口点 
//pNode GetCycleEntryNode(pList plist, pNode meet) 
//{
 
//  pNode pnode = plist; 
//  if ((plist == NULL) && (meet == NULL)) 
//  {
 
//      return NULL; 
//  } 
//  while (pnode != meet) 
//  {
 
//      meet = meet->next; 
//      pnode pnode->next; 
//  } 
//  return meet; 
//} 
void test1() 
{ 
pList plist; 
pNode ret = NULL; 
InitLinkList(&plist); 
PushBack(&plist, 1); 
PushBack(&plist, 2); 
PushBack(&plist, 3); 
PushBack(&plist, 4); 
PushBack(&plist, 5); 
PushBack(&plist, 6); 
//ret = FindKTailList(plist, 3); 
ret = EnterNodeOfLoop(plist); 
Display(plist); 
PrintNode(ret); 
Destroy(&plist); 
} 
int main() 
{ 
test1(); 
system("pause"); 
return 0; 
} 

【测试用例】
1、功能测试：
1）链表中包含环或不包含环；
2）链表中有多个或只有一个节点；
2、特殊输入测试：
链表头节点为NULL指针

【心得体会】
要学会把复杂的问题简单化，分布解决问题！

【存在的问题】
1、不会测试带环的链表！

2、//求环的入口点

pNode GetCycleEntryNode(pList plist, pNode meet) 
{ 
pNode pnode = plist; 
if ((plist == NULL) && (meet == NULL)) 
{ 
return NULL; 
} 
while (pnode != meet) 
{ 
meet = meet->next; 
pnode pnode->next; 
} 
return meet; 
}