问题
单链表可能有环,也可能无环。给定两个单链表的头节点head1和head2,这两个链表可能相交,也可能不相交。请实现一个函数,如果两个链表相交,请返回相交的第一个节点;如果不相交,返回null即可。
要求:
如果链表1的长度为 N,链表2的长度为 M,时间复杂度达到O( N+M),额外空 间复杂度请达到O(1)。
思路
两条单链表的相交情况
- 情况一: a链表有环,b链表无环
- 情况二: a链表无环,b链表无环
- 情况三: a链表有环,b链表有环
由链表本身的特点可得,情况一两链表是不可能相交的。故我们只需讨论情况二与情况三下面链表相交的形式。那么首先要解决的问题是,判断链表是否有环,根据两链表的有环情况调用相应的处理函数。
得到第一个相交节点的主函数
Node *getIntersectNode(Node *head1, Node *head2)
{
if (head1 == NULL || head2 == NULL)
{
return NULL;
}
Node *loop1 = getLoopNode(head1);
Node *loop2 = getLoopNode(head2);
if (loop1 == NULL && loop2 == NULL)
{
return noLoop(head1, head2);
}
if (loop1 != NULL && loop2 != NULL)
{
return bothLoop(head1, loop1, head2, loop2);
}
return NULL;
}
返回入环节点
有两种策略可以得到链表的入环节点,分别是hash表和快慢指针。使用hash表的实现比较简单,我们只需将遍历的节点用map保存起来。在访问下一个节点之前,先查询是否已保存,若map中已存在该节点,那么此节点为入环节点将它返回即可。
下面简单地介绍一下,使用快慢指针如何得到入环节点。已知,在有环链表中,使用快慢指针从头节点开始出发,一定会相遇于某个节点node1。现将node1与head两节点同时向下遍历,两节点第一次相遇的节点即为第一个入环节点。
这是一个小结论,很容易用数学证明,就不再此处展开。
代码如下:
Node *getLoopNode(Node *head)
{
//边界条件的判定
if (head == NULL || head->next == NULL || head->next->next == NULL)
{
return NULL;
}
Node* n1 = head->next; // n1 -> slow
Node* n2 = head->next->next; // n2 -> fast
while (n1 != n2)
{
//指针使用前,必须判空
if (n2->next == NULL || n2->next->next == NULL)
{
return NULL;
}
n2 = n2->next->next;
n1 = n1->next;
}
n2 = head; // n2 -> walk again from head
//相遇处节点与head节点同时向下遍历,有环则必定相遇于入环节点
while (n1 != n2)
{
//有环链表,此处无需判空
n1 = n1->next;
n2 = n2->next;
}
return n1;
}
两无环链表
两无环链表有两种拓扑结构
两链表平行
两链表相交(呈Y型)
两链表相交为什么不能呈X型,原因很简单。hint:仍是链表的结构特点所决定的
Node* noLoop(Node* head1, Node* head2)
{
if (head1 == NULL || head2 == NULL)
{
return NULL;
}
Node *cur1 = head1;
Node *cur2 = head2;
int n = 0;
//next非空时,继续向下遍历,直到遍历结尾
while (cur1->next != NULL)
{
n++;
cur1 = cur1->next;
}
while (cur2->next != NULL)
{
n--;
cur2 = cur2->next;
}
if (cur1 != cur2)
{
return NULL;
}
//长链表为cur1,短链表为cur2,n为两链表长度差
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = abs(n);
//长链表先走n步长
while (n != 0)
{
n--;
cur1 = cur1->next;
}
while (cur1 != cur2)
{
if (cur1 == NULL || cur2 == NULL)
{
return NULL;
}
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
两有环链表
具体实现见代码注释,清晰明了。有一个地方值得注意的是,当两入环节点不同时,返回两个node其中任一一个都行。理解的方式不同而已,都可以当作第一个相交节点。
Node *bothLoop(Node *head1, Node *loop1, Node *head2, Node *loop2)
{
Node *cur1 = NULL;
Node *cur2 = NULL;
//两入环节点相同,两链表在“入环处以上”相交
//处理方式类似于两无环链表,不同的是,遍历到入环节点处终止
if (loop1 == loop2)
{
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1)
{
n++;
cur1 = cur1->next;
}
while (cur2 != loop2)
{
n--;
cur2 = cur2->next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
abs(n);
while (n != 0)
{
n--;
cur1 = cur1->next;
}
while (cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
else
{
//从第一个入环节点向下遍历,再一次回到第一个入环节点之前
//若遍历过程中与第二个入环节点相遇,则返回其中任意一个作为相交节点
cur1 = loop1->next;
while (cur1 != loop1)
{
if (cur1 == loop2)
{
return loop1;
}
cur1 = cur1->next;
}
return NULL;
}
}