【练习】链表面试题（三）进阶

巩固一下基础，我重新写了一下无头节点单链表及链表面试题。我会分为入门，基础，进阶三章进行总结，点击以下蓝色字直接跳转对应章节。

链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶

• 判断单链表是否带环？若带环，求环的长度？求环的入口点？
  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;
}

测试用例

1. 链表中包含环
2. 链表中不包含环
3. 链表有多个或只有一个节点
4. 空链表

//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 空）
};

链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶