Question

单链表三(判断一单链表是不是循环单链表)

Answer 1

单链表的算法:给定一个单链表，它可能是一个以NULL结尾的非循环链表，也可能是一个循环结构的循环链表。已知这个链表的头指针，请编写一个函数来判断该链表属于哪类情况，该函数不得对链表本身做任何修改。 用两个指针同时遍历检查，快指针+满指针；当快指针超过满指针就是一个循环链表。让快慢两个指针从链表的头元素开始遍历，无限循环 如果快指针遇到了NULL指针 返回，这是个非循环链表 如果快指针追上了或者是超过慢指针 返回，这是一个循环链表 让慢指针前进一个节点 让快指针前进两个节点int DetermineTermination(LinkList head){ LinkList fast,slow;//快慢指针 fast=head; slow=head; while(1) { if(!fast||!fast->Next) return 0; slow=slow->Next; fast=fast->Next->Next; if(fast==slow||fast->Next==slow) return 1; }}void CricleLinkList(LinkList& head){ LinkList temp; temp=head; while(temp->Next) { temp=temp->Next; } temp->Next=head->Next->Next;}int main(){ LinkList head=(LinkList)malloc(sizeof(Node)); head->Next=NULL; head=InitLinkList(9,head);// CricleLinkList(head); cout<<"Circle Or Not:"<<DetermineTermination(head->Next); return 0;}