一、链表无环判断是否相交
给定两个单链表(假设链表不存在环),表头分别为 head1 和 head2.判断两个链表是否相交, 如果不相交返回 NULL, 如果相交, 则给出相交的第一个交点。对题目进行简单分析后不难得出,因为链表的特殊存储结构,使得其在存储结构上如果交叉则一定为“Y”型或者为“V”型,不可能为“X”型。所以相交只需求出第一个交点。
思路:可以先找到链表p1,p2的最后一个节点(各自遍历),同时记录节点数量a,b;然后判断最后一个节点是否相同,如果不相同则没相交;如果相同,则从第一个节点和|a-b|+1个节点开始比较看是否相等,不相等都寻找下一个节点直到找到交叉点。
判断两个链表是否相交有什么用呢?这是因为一旦两个链表出现相交的情况,就可能发生这样的情况,程序释放了链表La的所有节点,这样就导致了另外一个与之有相交节点的链表Lb中的节点也释放了,而Lb的使用者,可能并不知道事实的真相,这会带来很大的麻烦。
-
Node * list_cross(Node *head1,Node *head2)
-
{
-
int len1=0,len2=0,len=0;
-
int i=0;
-
Node *p,*q;
-
Node *tail1,*tail2;
-
tail1=NULL;
-
tail2=NULL;
-
p=head1;
-
q=head2;
-
while(p!=NULL)
-
{
-
len1++;
-
tail1=p;
-
p=p->link;
-
}
-
while(q!=NULL)
-
{
-
len2++;
-
tail2=q;
-
q=q->link;
-
}
-
if(tail1!=tail2) /// 没有交叉。
-
return NULL;
-
p=(len1>=len2?head2:head1);
-
q=(len1>=len2?head1:head2);
-
len=abs(len1-len2)+1;
-
/// 有交叉。
-
while(q!=NULL) /// 将长链表长的一部分走完,之后就能一起走到交点。
-
{
-
i++;
-
if(i==len)
-
break;
-
q=q->link;
-
}
-
while( p!=NULL)////此时两个链表等长开始比较。
-
{
-
if(p!=q)
-
{
-
p=p->link;
-
q=q->link;
-
}
-
else
-
return p;
-
}
-
}
二、链表有环。
怎样判断链表中是否存在环,并且找到环的开始节点呢?
网上有这样的一个解法:设置两个指针fast和slow,初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表),这样就可以判断两个链表是否相交了,程序如下:
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);
}
下面看看怎么找环的入口,当fast与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr
s= nr
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点(从相遇点向后遍历循环回到入口点的距离),于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇点为环入口点,也即为两个链表的第一个相同节点。程序描述如下:
-
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;
-
}
阅读(2990) | 评论(0) | 转发(1) |