欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言实现单链表面试题(进阶篇)

程序员文章站 2023-10-28 19:39:10
首先给出单链表的结构,下面实现具体代码 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. 都带环:入口点在环外,入口点在环内。
所有情况如下图所示
C语言实现单链表面试题(进阶篇)

复杂链表的复制

复杂链表的构建如上面已经给出

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);

}

这些是实现链表的面试题中较为复杂的了,链表重要的就是逻辑,把主要过程理解清楚。