C语言实现单链表面试题(进阶篇)
程序员文章站
2022-06-10 18:36:14
首先给出单链表的结构,下面实现具体代码
typedef int datatype;
typedef struct node
{
datatype data;
stru...
首先给出单链表的结构,下面实现具体代码
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 ("\n"); } 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); }
这些是实现链表的面试题中较为复杂的了,链表重要的就是逻辑,把主要过程理解清楚。