链表的面试题

时间:2022-06-25 09:42:08

1、比较顺序表和链表的优缺点,它们分别在什么场景下使用?
1)顺序表支持随机访问,单链表不支持随机访问。
2)顺序表插入/删除数据效率很低,时间复杂度为O(N)(除尾插和尾删),单链表插入/删除效率更高,时间复杂度为O(1)。
3)顺序表的CPU高速缓冲效率更高,单链表CPU高速缓冲效率低。

2、打印单向链表

void Display(pList plist)
{
pNode cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("over\n");
}

3、单链表的排序

void BubbleSort(pList *pplist)
{
pNode cur = NULL;
pNode tail = NULL;
assert(pplist);
if ((*pplist == NULL) || (*pplist)->next == NULL)
{
return;
}
cur = *pplist;
while (cur != tail)
{
while (cur->next != tail)
{
if (cur->data > cur->next->data)
{
DataType tmp = cur->data;
cur->data = cur->next->data;
cur->next->data = tmp;
}
cur = cur->next;
}
tail = cur;
cur = *pplist;
}
}

4、逆序打印单项链表

void ReversePrint(pList plist)
{
pNode cur = plist;
if (cur == NULL)
{
return;
}
if (cur->next != NULL)
{
ReversePrint(cur->next);
}
printf("%3d", cur->data);
}

5、删除无头单链表的非尾结点

void EraseNotTail(pNode pos)
{
pNode del = NULL;
assert(pos);
assert(pos->next != NULL);
pos->data = pos->next->data;
del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}

6、在无头单链表的非头结点前插入一个元素

void InsertFrontNode(pNode pos, DataType x)
{
pNode newnode = NULL;
DataType tmp;
assert(pos);
newnode = BuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
tmp = pos->data;
pos->data = pos->next->data;
pos->next->data = tmp;
}

7、约瑟夫环问题

void JosephCycle(pList *pplist, int k)
{
pNode cur = NULL;
pNode del = NULL;
assert(pplist);
cur = *pplist;
while (cur->next != cur)//留一个数
{
int i = 0;
for (i = 0; i < k - 1; i++)
{
cur = cur->next;
}
del = cur->next;
printf("%d", cur->data);
cur->data = cur->next->data;
cur->next = cur->next->next;
free(del);
del = NULL;
}
printf("%d\n", cur->data);
}

8、逆序单向链表

void ReverseList(pList *pplist)
{
DataType tmp = NULL;
pNode Next = NULL;
pNode cur = NULL;
assert(pplist);
if ((*pplist == NULL) || (*pplist)->next == NULL)
{
return;
}
cur = *pplist;
Next = cur->next;
cur->next = NULL;
while (Next != NULL)
{
tmp = Next->next;
Next->next = cur;
cur = Next;
Next = tmp;
}
*pplist = cur;
}

9、合并两个有序列表

pList Merge(const pList *p1, const pList *p2)
{
pList newlist = NULL;
pList list1 = NULL;
pList list2 = NULL;
pList tail = NULL;
assert(p1 && p2);
list1 = *p1;
list2 = *p2;
if (list1 == list2)//同为一条链表,或都为空链表
{
return NULL;
}
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
if (list1->data < list2->data)//新链表的首部
{
newlist = list1;
list1 = list1->next;
}
else
{
newlist = list1;
list1 = list1->next;
}
tail = newlist;
while (list1 && list2)
{
if (list1->data && list2->data)
{
tail->next = list1;
list1 = list1->next;
tail = tail->next;
}
else
{
tail->next = list2;
list2 = list2->next;
tail = tail->next;
}
}
if (list1 = NULL)
{
tail->next = list2;
}
else
{
tail->next = list1;
}
return newlist;
}

10、查找单链表的中间节点,要求只能遍历一次链表
//定义两个指针分别为fast和slow,fast每次跳两下,slow每次跳一下,
//当fast指向链尾时,show所指的位置就是中间结点

pNode FindMidNode(pList plist)
{
pNode fast = plist;
pNode slow = plist;
while (fast && (fast->next))
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}

11、查找单链表的倒数第k个节点,要求只能遍历一次链表
//定义两个指针分别为fast和slow,让fast先走k-1步后slow再走,当fast指向尾部时,slow所指向的就是倒数第k个元素

pNode FindKNode(pList plist, int k)
{
pNode fast = plist;
pNode slow = plist;
while (fast && fast->next)
{
if (--k <= 0)//k次后,slow再走
{
slow = slow->next;
}
fast = fast->next;
}
if (k <= 0)//执行完while后才能输出
{
return slow;
}
return NULL;
}

12、判断链表带环情况
//定义两个指针分别为fast和slow,每次fast比slow多走一步,如果带环,那么它们一定相交

pNode CheckCircle(pList plist)
{
pNode fast = plist;
pNode slow = plist;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)//带环
{
return fast;
}
}
return NULL;
}

13、求环的长度

int GetCircleLength(pNode meet)
{
pNode pnode = meet->next;//meet为相遇点
int i = 1;
while (pnode != meet)
{
pnode = pnode->next;
i++;
}
return i;
}

14、求环的入口点

pNode GetCycleEntryNode(pList plist, pNode meet)
{
pNode pnode = plist;
if ((plist == NULL) && (meet == NULL))
{
return NULL;
}
while(pnode != meet)
{
meet = meet->next;
pnode = pnode->next;
}
return meet;
}

15、判断两条单项链表是否相交

int CheckCross(pList list1, pList list2)
{
pNode p1 = list1;
pNode p2 = list2;
while (p1 && p1->next)
{
p1 = p1->next;
}
while (p2 && p2->next)
{
p2 = p2->next;
}
if ((p1 == p2) && (p1 != NULL))//相交
{
return 1;
}
else
return -1;
}

16、转化成不带环的链表求解

pNode GetCrossNoCycle(pList list1, pList list2)
{
pNode meet = NULL;
pNode cur = list1;
pNode crossNode = NULL;
while (cur && cur->next)
{
cur = cur->next;
}
cur->next = list2;
meet = CheckCircle(list1);
crossNode = GetCycleEnterNode(list1, meet);
return crossNode;
}

17、求交点

pNode GetCrossNode(pList list1, pList list2)
{
pNode p1 = CheckCircle(list1);//1表带环;0表不带环
pNode p2 = CheckCircle(list2);
pNode crossNode = NULL;
if (p1 == NULL && p2 == NULL)//不带环
{
crossNode = GetCrossNoCycle(list1, list2);
return crossNode;
}
else if (p1 && p2)
{
pNode endNode = NULL;
pNode cur = NULL;
//找到环入口的第一个结点
endNode = GetCycleFrontEntryNode(list1, p1);
cur = endNode->next;//保存环的入口
endNode->next = NULL;//将环断开成两个不带环的链表
crossNode = GetCrossNoCycle(list1, list2);
endNode->next = cur;
}
return crossNode;
}