给出两个单向链表的头指针,判断这两个链表是否相交,如果相交给出相交的第一个结点 一、两个链表均不含有环 链表相交如下图
方法一:直接法 直接判断第一个链表的每个结点是否在第二个链表中,时间复杂度为O(len1*len2),耗时很大 方法二:利用计数 如 果 两个链表相交,则两个链表就会有共同的结点;而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点,就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序,建立hash表,然后针对第二个链表的每个节点的地址查询hash表,如果它在hash表中出现,则说明两个链表有共 同的结点。这个方法的时间复杂度为:O(max(len1+len2);但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度,增加 了存储空间。 以链表节点地址为值,遍历第一个链表,使用Hash保存所有节点地址值,结束条件为到最后一个节点(无环)或Hash中该地址值已经存在(有环)。 再遍历第二个链表,判断节点地址值是否已经存在于上面创建的Hash表中。 这个方面可以解决题目中的所有情况,时间复杂度为O(m+n),m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型,假设链表都是在堆中动态创建的,可以使用堆的起始地址作为偏移量,以地址减去这个偏移量作为Hash函数 方法三 两个没有环的链表相交于一节点,则在这个节点之后的所有结点都是两个链表所共有的。如果它们相交,则最后一个结点一定是共有的,则只需要判断最后一个结点是否相同即可。时间复杂度为O(len1+len2)。对于相交的第一个结点,则可求出两个链表的长度,然后用长的减去短的得到一个差值 K,然后让长的链表先遍历K个结点,然后两个链表再开始比较。还可以这样:其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个 /************************************************************************/ struct LinkList//链表结构体 void InsertList(LinkList *&list)//建立一个链表 newNode=(LinkList *)malloc(sizeof(LinkList)); head->next=newNode;
int main() int flen=0,slen=0,len; InsertList(first);//构造第一个链表 ///////////////////////////////////////////////// h1=first->next; { h2=second->next; if(flen>=slen)//求两个链表长度的差值 h1=h1->next; while(1) { 结果:
二、链表中含有环
链表中有环如下图:
1.链表中是否有环的判断
可以设置两个指针(fast,slow),初始值均指向头,slow每次向前一步,fast每次向前两步;
如果链表中有环,则fast先进入环中,而slow后进入环中,两个指针在环中必定相遇;
如果fast遍历到尾部为NULL,则无环
2.链表有环,判断环的入口点
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr 设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。 (L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点
因而,可以在链表头,相遇点分别设定一个指针,每次各走一步,两个指针必定相遇,则相遇第一点为环入口点。
LinkList * ListLoop(LinkList *list) //判断一个链表中是否有环
{ int isLoop=0; LinkList *fast,*slow; fast=list; slow=list; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next;//fast每次两步,slow每次一步 if(fast==slow) //当两指针相等时,判断链表中有环 { isLoop=1; break; } } if(isLoop==1)//链表中有环时 { slow=list; while(slow!=fast)//一个头指针,一个相遇点指针,两个第一次相等时为环入口点 { slow=slow->next; fast=fast->next; } return slow; } else { cout<<"链表中没有环"; return NULL; } } 当两个链表中有环时,相交的判断:
(1)首先分别找出两个链表入环的第一个结点记为p1,p2
(2)如果p1==p2,说明两个链表在入环之前或入环的第一个结点相交;则此时可以转为两个链表均不带环相交的判断,把p1,p2当作最后的末尾结点
(3)如果p1!=p2,此时两个链表可能完全不相交;也可能两个链表完全共有同一个环。
此时,判断p1->next与p2->next是否相等,如果相等则两链表完全共环;如果不相等,则完全不相交。
当一个链表中有环,一个链表中没有环时,两个链表必不相交。 判断两个链表是否相交:(假设两个链表都没有环) 1、判断第一个链表的每个节点是否在第二个链表中 2、把第二个链表连接到第一个后面,判断得到的链表是否有环,有环则相交 3、先遍历第一个链表,记住最后一个节点,再遍历第二个链表,得到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交 如何判断一个单链表是有环的?(注意不能用标志位,最多只能用两个额外指针) 扩展问题参考:http://hi.baidu.com/azuryy/blog/item/18e85b02ec34a4094bfb51de.html list1 head: p1 p1 = p1->next; 扩展2:求两个链表相交的第一个节点 Node* step( Node* p, Node* q) 有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。 bool IsExitsLoop(slist *head)
{ slist *slow = head, *fast = head; while ( fast && fast->next ) { slow = slow->next; fast = fast->next->next; if ( slow == fast ) break; } return !(fast == NULL || fast->next == NULL); }
slist* FindLoopPort(slist *head)
{ slist *slow = head, *fast = head; while ( fast && fast->next ) { slow = slow->next; fast = fast->next->next; if ( slow == fast ) break; } if (fast == NULL || fast->next == NULL) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }
|
|