摘要：
=见面）//{cur=cur-˃next；Meet=Meet-˃next；}returncur；}可以根据图纸进行分析判断两个链表是否相交。如果它们相交，请找到交点。pNodeCheckCrossNode{pNodecur1=l1；pNodetail=l1；p Noderet=NULL；而{tail=tail-˃next；}tail-˃next=l2；ret=IfRing；returnret；}判断两个链接列表是否相交。如果它们相交，请找到交点。想法：1。首先，你应该判断链表是否有环：没有环，只有一个有环。2.两者都有一个环：入口点在环外，入口点在圈内。
首先给出单链表的结构，下面实现具体代码
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node*next;
}Node,*pNode,*pList;//结点
typedef struct ComplexNode
{
DataType D;
struct ComplexNode*next;
struct ComplexNode*random;
}ComplexNode,*pComplexNode;
判断单链表是否带环，若带环，求环的长度，求环的入口点
- 判断是否带环
pNode IfRing(pList plist)//判断单链表是否带环,返回交点
{
pNode slow = plist;
pNode fast = plist;
//是否带环
while (fast&&fast->next)//注意边界问题
{
slow = slow->next;
fast = fast->next->next;
if (fast == slow)//如果相遇，则带环
{
return fast;
}
}
return NULL;
}
- 求换的长度
int GetCircleLen(pNode meet)//求环的长度
{
pNode cur = meet;
int count = 0;
do
{
count++;
cur = cur->next;
} while (cur!=meet);
return count;
}
- 求环的入口点
pNode GetCircleEntry(pList plist,pNode meet)//求环的入口点
{
pNode cur = plist;
pNode fast = plist;
pNode slow = plist;
while(cur!=meet)//根据画图可分析出
{
cur = cur->next;
meet = meet->next;
}
return cur;
}判断两个链表是否相交，若相交，求交点。（假设链表不带环）
pNode CheckCrossNode(pList l1,pList l2)
{
pNode cur1 = l1;
pNode tail = l1;
pNode ret = NULL;
while(tail->next)
{
tail = tail->next;
}
tail->next = l2;
ret = IfRing(l1);
return ret;
}判断两个链表是否相交，若相交，求交点。（假设链表可能带环也可能不带环）
思想：
1. 首先应判断链表是否带环：都不带环，只有一个带环
2. 都带环：入口点在环外，入口点在环内。
所有情况如下图所示
复杂链表的复制
复杂链表的构建如上面已经给出
ComplexNode CrecteComplexNode(DataType d)//这里创建复杂链表的结点
{
pComplexNode newNode = (pComplexNode)malloc(sizeof(ComplexNode));
if (newNode == NULL)
{
perror("malloc");
return NULL;
}
newNode->D = d;
newNode->next = NULL;
newNode->random = NULL;
return newNode;
}
void PrintComplexList(pComplexNode head)
{
pComplexNode cur = head;
while(cur)
{
printf ("%d-->",cur->D);
printf ("random-->[%d]--->next",cur->random->D);
cur = cur->next;
}
printf ("
");
}
pComplexNode CloneComplexNode(pComplexNode head)//复制复杂链表
{
pComplexNode cur = head;
pComplexNode tmp = NULL;
pComplexNode copy = NULL;
pComplexNode tail = NULL;
while(cur)
{
pComplexNode newnode = CrecteComplexNode(cur->D);
tmp = cur;
cur= cur->next;
newnode->next = cur;
tmp->next = newnode;
}//复制每个节点并插入到节点后
cur = head;
while(cur)
{
cur->next->random = cur->random->next;
cur = cur->next->next;
}//调整random指针
cur = head;
copy= cur->next;
tail = copy;
while(tail->next)
{
tail->next = tail->next->next;
cur->next = tail->next;
cur = cur->next;
tail = tail->next;
cur->next = NULL;
return copy;
}
}
//下面给出具体的测试代码
void test3()
{
pComplexNode pNode1 = CrecteComplexNode(1);
pComplexNode pNode2 = CrecteComplexNode(2);
pComplexNode pNode3 = CrecteComplexNode(3);
pComplexNode pNode4 = CrecteComplexNode(4);
pComplexNode pNode5 = CrecteComplexNode(5);
pNode1->next = pNode2;
pNode2->next = pNode3;
pNode3->next = pNode4;
pNode1->random = pNode4;
pNode2->random = pNode1;
pNode3->random = pNode2;
pNode4->random = pNode2;
CloneComplexNode(pNode1);
PrintComplexList(pNode1);
}这些是c语言实现链表的面试题中较为复杂的了，链表重要的就是逻辑，把主要过程理解清楚。