巩固一下基础，我重新写了一下无头节点单链表及链表面试题。我会分为入门，基础，进阶三章进行总结，点击以下蓝色字直接跳转对应章节。
链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶
- 判断单链表是否带环？若带环，求环的长度？求环的入口点？
3个步骤：1. 找出换种任意一个节点；2. 得到环中节点个数；3. 找到入口点
判断是否带环 只遍历一次 时间复杂度O(n)
//判断单链表是否带环？
pNode MeetNode(pList plist)
{
assert(plist);
pNode slow = plist;
pNode fast = plist;
while (fast && slow)
{
if (fast == slow && fast != plist)
return slow;
slow = slow->next;
fast = fast->next->next;
if(fast)
fast = fast->next->next;
}
return NULL;
求长度、入口点 时间复杂度小于 O(n^3)
//若带环，求环的长度？求环的入口点？
pNode EntryNodeOfLoop(pList plist)
{
assert(plist);
pNode meet = MeetNode(plist);
int i = 0;
//求环的长度
int count = 1;
pNode cur = meet;
while (meet != cur->next)
{
cur = cur->next;
count++;
}
//入口点
pNode fast = plist;
pNode slow = plist;
for (i = 0; i < count; ++i)
{
fast = fast->next;
}
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
测试用例
- 链表中包含环
- 链表中不包含环
- 链表有多个或只有一个节点
- 空链表
//testMeetNode
void testMeetNode()
{
pNode cur = NULL;
pNode set = NULL;
int count = 1;
pList plist;
InitList(&plist);
PushBack(&plist, 1);
PushBack(&plist, 2);
PushBack(&plist, 3);
PushBack(&plist, 4);
PushBack(&plist, 5);
PushBack(&plist, 6);
PrintList(plist);
//加环
cur = plist;
set = plist->next->next;
while (cur->next)
cur = cur->next;
cur->next = set;
pNode meetnode = MeetNode(plist);
if (meetnode)
{
printf("the meet node is: %d \n", meetnode->data);
printf("the entry node of loop is: %d \n", EntryNodeOfLoop(plist)->data);
}
else
printf("no loop!\n");
//空节点test
/*pNode meetnode = MeetNode(NULL);
if (meetnode)
{
printf("the meet node is: %d \n", meetnode->data);
printf("the entry node of loop is: %d \n", EntryNodeOfLoop(NULL)->data);
}
else
printf("no loop!\n");*/
// DestroyList(&plist);
}
- 判断两个链表是否相交，若相交，求交点。（假设链表** 不带环 **）
//判断两个链表是否相交，若相交，求交点。（假设链表不带环）
pNode isIntersect(pList list1, pList list2)
{
pNode cur1 = list1;
pNode cur2 = list2;
int count1 = 0;
int count2 = 0;
int dff = 0;
int i = 0;
if (list1 == NULL || list2 == NULL)
return NULL;
while (cur1->next)
{
cur1 = cur1->next;
count1++;
}
while (cur2->next)
{
cur2 = cur2->next;
count2++;
}
dff = abs(count1 - count2);
if (count1 > count2)
{
cur1 = list1;
cur2 = list2;
for (i = 0; i < dff; i++)
{
cur1 = cur1->next;
}
while (cur1->next && cur2->next && cur1->data != cur2->data)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
}
else
{
cur1 = list1;
cur2 = list2;
for (i = 0; i < dff; i++)
{
cur2 = cur2->next;
}
while (cur1->next && cur2->next && cur1->data != cur2->data)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
}
if (cur1->data == cur2->data)
return cur1;
else
return NULL;
}
test_isIntersect.c
void test_isIntersect()
{
pNode cur = NULL;
pNode pos = NULL;
pList plist1;
pList plist2;
InitList(&plist1);
InitList(&plist2);
PushBack(&plist1, 1);
PushBack(&plist1, 3);
PushBack(&plist1, 5);
PushBack(&plist1, 7);
PushBack(&plist1, 9);
PrintList(plist1);
PushBack(&plist2, 2);
PushBack(&plist2, 4);
PushBack(&plist2, 6);
PrintList(plist2);
//不相交
if (pos = isIntersect(plist1, plist2))
printf("Intersect is %d\n", pos->data);
else
printf("not is Intersect\n");
//相交
cur = plist2;
while (cur->next)
cur = cur->next;
cur->next = plist1->next->next;
PrintList(plist2);
if (pos = isIntersect(plist1, plist2))
printf("Intersect is %d\n", pos->data);
else
printf("not is Intersect\n");
}
- 判断两个链表是否相交，若相交，求交点。（假设链表可能** 带环 **）
//判断两个链表是否相交，若相交，求交点。（假设链表可能带环）
pNode isIntersectL(pList list1, pList list2)
{
pNode cur1 = list1;
pNode cur2 = list2;
int count1 = 0;
int count2 = 0;
int dff = 0;
int i = 0;
//判断链表是否为空
if (list1 == NULL || list2 == NULL)
return NULL;
//看两条链表是否有环
pNode pos1 = MeetNode(list1);
pNode pos2 = MeetNode(list2);
if (!pos1 && pos2 || pos1 && !pos2)//只有一个有环 肯定不相交
return NULL;
else if (pos1 && pos2) // 两个都有环
{
//判断是不是一个环
Node* tmp = pos1;
do
{
if (pos2 == pos1 || pos2 == pos1->next)
break;
pos2 = pos2->next->next;
pos1 = pos1->next;
} while (tmp == pos1);
if (pos1 != pos2 && pos1->next != pos2) // 不是一个环肯定不相交
return NULL;
//是一个环
while (cur1 != pos1)
{
cur1 = cur1->next;
count1++;
}
while (cur2 != pos1)
{
cur2 = cur2->next;
count2++;
}
dff = abs(count1 - count2);
if (count1 > count2)
{
cur1 = list1;
cur2 = list2;
for (i = 0; i < dff; i++)
{
cur1 = cur1->next;
}
while (cur1->data != cur2->data)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
}
else
{
cur1 = list1;
cur2 = list2;
for (i = 0; i < dff; i++)
{
cur2 = cur2->next;
}
while (cur1->data != cur2->data)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
}
if (cur1->data == cur2->data)
return cur1;
else
return NULL;
}
else // 两个都没环
return isIntersect(list1, list2);
}
test_isIntersectL.c
void test_isIntersectL()
{
pNode cur1 = NULL;
pNode cur2 = NULL;
pNode pos = NULL;
pNode set = NULL;
pList plist1;
pList plist2;
InitList(&plist1);
InitList(&plist2);
PushBack(&plist1, 1);
PushBack(&plist1, 3);
PushBack(&plist1, 5);
PushBack(&plist1, 7);
PushBack(&plist1, 9);
//PrintList(plist1);
PushBack(&plist2, 0);
PushBack(&plist2, 2);
PushBack(&plist2, 4);
PushBack(&plist2, 6);
//PrintList(plist2);
//不相交
/*if (pos = isIntersect(plist1, plist2))
printf("Intersect is %d\n", pos->data);
else
printf("not is Intersect\n");*/
//相交
cur2 = plist2;
while (cur2->next)
cur2 = cur2->next;
cur2->next = plist1->next->next;
//PrintList(plist2);
//加环
cur1 = plist1;
set = plist1->next->next;
while (cur1->next)
cur1 = cur1->next;
cur1->next = set;
//PrintList(plist1);
//PrintList(plist2);
if (pos = isIntersectL(plist1, plist2))
printf("Intersect is %d\n", pos->data);
else
printf("not is Intersect\n");
}
- 复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。
** 复杂链表的结构 **
//ps: 复杂链表的结构
struct ComplexNode
{
int _data ; // 数据
struct ComplexNode * _next; // 指向下一个节点的指针
struct ComplexNode * _random; // 指向随机节点（可以是链表中的任意节点 or 空）
};
网友评论