链表的基本操作在链接的博客中已经有实现https://blog.csdn.net/Damn_Yang/article/details/83689944

下面我们来看看链表相关的面试题，非常重要

下面的题目都会一个一个实现

#include<stdio.h>
typedef int DataType;

typedef struct Node
{
    DataType data;
    struct Node * next;
}Node, *pNode, LinkList, *pLinkList;

//比较顺序表和链表的优缺点 

//从尾到头打印链表
void PrintLinkTailToHead(pLinkList ppl, stack* s);

//删除一个无头单链表的非尾结点
void RmoveNodeNotTail(pLinkList *ppl, pNode pos);

//用链表实现约瑟夫环
void JosephCircle(pLinkList *ppl, int k);

//在无头单链表的一个节点前插入一个节点(不能遍历链表)
void InsertNodeNotHead(pLinkList *ppl, DataType data, pNode pos);

//链表的逆置
void Reverselist(pLinkList *ppl);

//链表的冒泡排序
void BubbleSort(pLinkList *ppl);

//合并两个有序的链表，合并后依然有序
pNode Merge(pLinkList* list1, pLinkList* list2);

//合并两个有序的链表(递归版本)
pNode Merge_R(pLinkList list1, pLinkList list2);

//求单链表中间结点
pNode FindMidNode(pLinkList plist);

//求单链表倒数第K个结点
pNode FindLastKNode(pLinkList plist, int k);

//判断链表是否带环，带环返回相遇点，不带环返回NULL
pNode IsCircle(pLinkList plist);

//求环的长度
int GetCircleLength(pNode meet);

//求环的入口点
pNode GetCircleEntryNode(pLinkList plist, pNode meet);

//判断链表是否相交(假设链表不带环)，相交返回1，不相交返回0
int IsCross(pLinkList plist1, pLinkList plist2);

//求两个链表的交点
pNode GetMeetNode(pLinkList plist1, pLinkList plist2);

//求两个链表中相同的数据(交集)
void UnionSet(pLinkList plist1, pLinkList plist2);

1.比较顺序表和链表的优缺点

1.顺序表：
原理：顺序表存储是将数据元素放到一块连续的内存存储空间，存取效率高，速度快。但是不可以动态增加长度
优点：存储速度高效，可以通过下标来直接存储，创建而简单。
缺点：1.插入和删除比较慢，2.不可以增长长度
2.链表：
原理：链表存储是在程序运行过程中动态的分配空间，只要存储器还有空间，就不会发生存储溢出问题
优点：插入删除比较快，可以用不连续的空间
缺点：查找速度慢，因为需要遍历。

2.从尾到头打印单链表

//2.从尾到头打印链表
void PrintLinkTailToHead(pLinkList ppl)
{
    pNode tail = NULL;
    while (ppl != tail)
    {
        pNode cur = ppl;
        while (cur->next != tail)
        {
            cur = cur->next;
        }
        printf("%d ", cur->data);
        tail = cur;
    }
}

3.删除一个无头单链表的非尾结点

//3.删除一个无头单链表的非尾结点
void RmoveNodeNotTail(pLinkList *ppl, pNode pos)
{
    pNode del = NULL;
    pos->data = pos->next->data;//复制数据
    del = pos->next;//改变要删除的节点
    pos->next = del->next;//删除下一个节点
    free(del);
    del = NULL;
}

4.用链表实现约瑟夫环

//4.用链表实现约瑟夫环
void JosephCircle(pLinkList *ppl, int k)
{
    pNode tmp = *ppl;
    pNode cur = *ppl;
    pNode del = NULL;
    //将单链表弄成一个环
    while (tmp->next)
    {
        tmp = tmp->next;
    }
    tmp->next = *ppl;

    while (cur != cur->next)
    {
        int count = k;
        //走k-1步，清除一个
        while (--count)
        {
            cur = cur->next;
        }
        del = cur->next;
        printf("删除：%d \n", cur->data);
        cur->data = cur->next->data;//复制数据
        cur->next = del->next;//删除下一个节点
        free(del);
        del = NULL;
    }
    printf("剩余：%d\n", cur->data);
}

5.在无头单链表的一个节点前插入一个节点(不能遍历链表)

//5.在无头单链表的一个节点前插入一个节点(不能遍历链表)
void InsertNodeNotHead(pLinkList *ppl, DataType data, pNode pos)
{
    pNode newNode = NULL;
    newNode = BuyNode(pos->data);
    newNode->next = pos->next;
    pos->next = newNode;
    pos->data = data;
}

6.链表的逆置

//6.链表的逆置
void Reverselist(pLinkList *ppl)
{
    pNode cur = *ppl;
    pNode tmp = NULL;
    pLinkList head = NULL;
    if (*ppl == NULL || (*ppl)->next)
    {
        return;
    }
    while (cur)
    {
        tmp = cur->next;//保存下一个节点，否则会丢失链表后面的内容
        cur->next = head;
        head = cur;
        cur = tmp;
    }
    *ppl = head;
}

7.链表的冒泡排序

//7.链表的冒泡排序
void BubbleSort(pLinkList *ppl)
{
    pNode cur = *ppl;
    pNode tail = NULL;
    while (cur != NULL)//趟数
    {
        while (cur->next != NULL)//比较次数
        {
            if (cur->data > cur->next->data)
            {
                DataType tmp = cur->data;
                cur->next = cur->next->data;
                cur->next->data = tmp;
            }
            cur = cur->next;
        }
    }
    tail = cur;
    cur = *ppl;
}

8.合并两个有序的链表，合并后依然有序

//8.合并两个有序的链表，合并后依然有序
pNode Merge(pLinkList list1, pLinkList list2)
{
    pLinkList newhead = NULL;
    //一个链表为空，一个不为空
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    //两个链表都为空
    if ((list1 == NULL) && (list2 == NULL))
    {
        return NULL;
    }
    if (list1->data < list2->data)
    {
        newhead = list1;
        list1 = list1->next;
    }
    else
    {
        newhead = list2;
        list2 = list2->next;
    }
    //保存链表最后一个节点的位置
    pNode tail = newhead;
    //依次比较尾插
    while ((list1 != NULL) && (list2 != NULL))
    {
        if (list1->data < list2->data)
        {
            tail->next = list1;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    //将剩余的节点插入到新链表中
    if (list1 == NULL)
    {
        tail->next = list2;
    }
    else if (list2 == NULL)
    {
        tail->next = list1;
    }
    return newhead;
}

9.合并两个有序的链表(递归版本)

//9.合并两个有序的链表(递归版本)
pNode Merge_R(pLinkList list1, pLinkList list2)
{
    pLinkList newhead = NULL;
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    if ((list1 == NULL) && (list2 == NULL))
    {
        return NULL;
    }
    if (list1->data < list2->data)
    {
        newhead = list1;
        newhead->next = Merge_R(list1->next, list2);
    }
    else
    {
        newhead = list2;
        newhead->next = Merge_R(list2->next, list1);
    }
    return newhead;
}

10.求单链表中间结点

//10.求单链表中间结点
pNode FindMidNode(pLinkList plist)
{
    pNode first = plist;
    pNode second = plist;
    //链表没有节点或者只有一个节点返回
    if ((plist == NULL) || (plist->next == NULL))
    {
        return plist;
    }
    while ((second != NULL) && (second->next != NULL))
    {
        second = second->next->next;
        first = first->next;
    }
    return first;
}

11.求单链表倒数第K个结点

//11.求单链表倒数第K个结点
pNode FindLastKNode(pLinkList plist, int k)
{
    pNode slow = plist;
    pNode fast = plist;
    if (plist == NULL)
    {
        return plist;
    }
    //快指针走k-1步
    while (--k)
    {
        if (fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    //快慢指针一起走，快的到终点，慢指针则指向倒数第k个结点
    while (fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

12.判断链表是否带环，带环返回相遇点，不带环返回NULL

//12.判断链表是否带环，带环返回相遇点，不带环返回NULL
pNode IsCircle(pLinkList plist)
{
    pNode slow = plist;
    pNode fast = plist;
    if (plist == NULL)
    {
        return plist;
    }
    while ((fast != NULL) && (fast->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return slow;
        }
    }
    return NULL;
}

13.求环的长度

//13.求环的长度
int GetCircleLength(pNode meet)
{
    pNode cur = meet->next;
    int len = 1;
    while (cur != meet)
    {
        len++;
        cur = cur->next;
    }
    return len;
}

14.求环的入口点

//14.求环的入口点
pNode GetCircleEntryNode(pLinkList plist, pNode meet)
{
    pNode cur = plist;
    if (plist == NULL)
    {
        return NULL;
    }
    while (cur != meet)
    {
        cur = cur->next;
        meet = meet->next;
    }
    return cur;
}

15.判断链表是否相交(假设链表不带环)，相交返回1，不相交返回0

//15.判断链表是否相交(假设链表不带环)，相交返回1，不相交返回0
int IsCross(pLinkList plist1, pLinkList plist2)
{
    pNode cur1 = plist1;
    pNode cur2 = plist2;
    if ((plist1 == NULL) && (plist2 == NULL))
    {
        return 0;
    }
    while (cur1->next != NULL)
    {
        cur1 = cur1->next;
    }
    while (cur2->next != NULL)
    {
        cur2 = cur2->next;
    }
    if (cur1 == cur2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

16.求两个链表的交点

//16.求两个链表的交点
pNode GetMeetNode(pLinkList plist1, pLinkList plist2)
{
    int len1 = 0;
    int len2 = 0;
    int gaps = 0;
    pNode cur1 = plist1;
    pNode cur2 = plist2;
    while (cur1)//求链表一的长度
    {
        cur1 = cur1->next;
        len1++;
    }
    while (cur2)//求链表二的长度
    {
        cur2 = cur2->next;
        len2++;
    }
    cur1 = plist1;//长链表
    cur2 = plist2;//短链表
    gaps = len1 - len2;
    if (len1 < len2)
    {
        cur1 = plist2;
        cur2 = plist1;
    }
    //长链表走gaps步
    while (gaps--)
    {
        cur1 = cur1->next;
    }
    //一起走
    while (cur1 != cur2)
    {
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return cur1;
}

17.求两个链表中相同的数据(交集)

//17.求两个链表中相同的数据(交集)
void UnionSet(pLinkList plist1, pLinkList plist2)
{
    if ((plist1 == NULL) || (plist2 == NULL))
    {
        return;
    }
    while ((plist1 != NULL) && (plist2 != NULL))
    {
        if (plist1->data < plist2->data)
        {
            plist1 = plist1->next;
        }
        else if (plist1->data > plist2->data)
        {
            plist2 = plist2->next;
        }
        else
        {
            printf("%d ", plist1->data);
            plist1 = plist1->next;
            plist2 = plist2->next;
        }
    }
}