C语言实现单链表面试题（进阶篇）

首先给出单链表的结构，下面实现具体代码

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

}

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