链表的面试题详解编程语言

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