链表面试题总结

一.定义数据结构

typedef int DataType;

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

二.各题目函数声明

//从尾到头打印链表
void PrintLinkTailToHead(pLinkList pl);

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

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

//在无头单链表的一个节点前插入一个节点(不能遍历链表)
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）.从尾到头打印链表(题目来源：剑指offer)

https://blog.csdn.net/hansionz/article/details/80905962

void PrintLinkTailToHead(pLinkList pl,stack * s)
{
//（1）
#if 0
    if(pl != NULL)
    {
        if(pl->next != NULL)
        {
            PrintLinkTailToHead(pl->next);
        }
        printf("%d--->",pl->data);
    }
    /*if (pl == NULL)
    {
        return NULL;
    }
    PrintLinkTailToHead(pl->next);
    printf("%d--->", pl->data);*/
#endif
//(2)
#if 0
    pNode tail = NULL;
    while (pl != tail)
    {
        pNode cur = pl;
        while (cur->next != tail)
        {
            cur = cur->next;
        }
        printf("%d--->", cur->data);
        tail = cur;
    }
#endif
//(3)
    Node* cur = pl;
    while (cur != NULL)
    {
        s->data[s->top++] = cur->data;
        cur = cur->next;
    }
    while (s->top >= 0)
    {
        printf("%d--->", s->data[s->top--]);
    }
    printf("over\n");
}

（2）.删除一个无头单链表的非尾结点（不能遍历链表）(题目来源：剑指offer)

思路：要删除一个结点，就必须找到要删除结点的前驱。但是不能遍历链表，我们找不到前驱。我们试着改变一下思路，将要删除结点的下一个结点的数据复制给要删除的结点，而要删除的结点就变成了原来要删除结点的下一个结点。这样就很巧妙的删除了结点。
https://blog.csdn.net/hansionz/article/details/80934410

void RmoveNodeNotTail(pLinkList *ppl, pNode pos)
{
    pNode del = NULL;
    assert(ppl != NULL);
    assert(pos->next != NULL);
    assert(*ppl != NULL);
    pos->data = pos->next->data;//复制数据
    del = pos->next;//改变要删除的结点
    pos->next = del->next;//删除下一个结点
    free(del);
    del = NULL;
}

（3）.用单链表实现约瑟夫环问题

https://blog.csdn.net/hansionz/article/details/81539863

void JosephCircle(pLinkList *ppl, int k)
{
    assert(ppl != NULL);
    pNode cur = *ppl;
    pNode tmp = *ppl;
    pNode del = NULL;
    //将单链表连成一个换
    while (tmp->next)
    {
        tmp = tmp->next;
    }
    tmp->next = *ppl;
    //如果还有大于1个结点则继续查找
    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);
}

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

思路：既然不能遍历链表，说明找不到前驱，那我们只能先将这个结点插入到它的后边，然后在交换数据。或者，在开辟结点的时候就已前面结点的数据开辟，插入之后再将前面结点的数据域设置为已知数据，从而达到交换的效果。

void InsertNodeNotHead(pLinkList *ppl, DataType data, pNode pos)
{
    pNode newNode = NULL;
    assert(ppl != NULL);
    //（1）
#if 0
    DataType tmp = 0;
    newNode = BuyNode(data);
    newNode->next = pos->next;
    pos->next = newNode;
    tmp = newNode->data;
    newNode->data = pos->data;
    pos->data = tmp;
#endif
    //（2）
    newNode = BuyNode(pos->data);
    newNode->next = pos->next;
    pos->next = newNode;
    pos->data = data;
}

（5）.链表的逆置/反转

思路：重新开辟一条链表，然后依次取下原链表的每个结点头插入到新的链表中，新的链表就是逆置的结果

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

单独总结于另一边博客：
https://blog.csdn.net/hansionz/article/details/82285384

（6）.链表的冒泡排序

void BubbleSort(pLinkList *ppl)
{
    assert(ppl != NULL);
    pNode cur = *ppl;
    pNode tail = NULL;
    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 = *ppl;
    }
}

（7）.合并两个有序的链表，合并后依然有序

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

（8）.合并两个有序的链表，合并后依然有序(递归版本)

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(list1, list2->next);
    }
    return newhead;
}

（9）.求单链表中间结点

思路：利用快慢指针思想，快指针fast每次走两步，满指针slow每次走一步。当快指针做到最后一个结点时，慢指针正好指向中间结点。

pNode FindMidNode(pLinkList plist)
{
    pNode slow = plist;
    pNode fast = plist;
    //链表没有结点或者只有一个结点直接返回
    if ((plist == NULL) || (plist->next == NULL))
    {
        return plist;
    }
    //节点数为偶数时判断条件为fast!=NULL,此时中间节点为后面的那个;
    //为奇数时判断条件为fast->next!=NULL.
    while ((fast != NULL) && (fast->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

（10）.求单链表倒数第K个结点

思路：依然是利用快慢指针的方法，让快指针先走k-1步，然后快指针和慢指针一起出发，当快指针走到最后一个结点时，慢指针指向倒数第k个结点。

pNode FindLastKNode(pLinkList plist, int k)
{
    pNode fast = plist;
    pNode slow = plist;
    if (plist == NULL)
    {
        return plist;
    }
    //快指针走k-1步
    while (--k)
    {
        //如果链表总的节点数小于k,则肯定不存在倒数第k个结点
        if (fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    //快慢指针一起走，快的到终点，慢指针则指向倒数第k个结点
    while (fast->next != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

（11）.判断单链表是否带环，带环返回相遇点，不带环返回NULL

思路：依旧是快慢指针的思想，快指针一次走两步，慢指针一次走一步，如果单链表带环，则快指针和慢指针必然相遇。

//带环返回相遇点，不带环返回NULL
pNode IsCircle(pLinkList plist)
{
    pNode fast = plist;
    pNode slow = plist;
    if (plist == NULL)
        return NULL;
    while ((fast != NULL) && (fast->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return fast;
        }
    }
    return NULL;
}

（12）.求单链表中环的长度

思路：从相遇点的下一个结点开始便利一遍环，就可以求出来环的长度了。但是len必须是从1开始，否则会少计算相遇点那个结点。

int GetCircleLength(pNode meet)
{
    assert(meet != NULL);
    pNode cur = meet->next;
    int len = 1;
    //len必须从1开始，否则没有算meet那个结点
    while (cur != meet)
    {
        len++;
        cur = cur->next;
    }
    return len;
}

（13）.求单链表中求环的入口点

思路：

在这里插入图片描述

pNode GetCircleEntryNode(pLinkList plist, pNode meet)
{
    pNode cur = plist;
    if (plist == NULL)
    {
        return NULL;
    }
    assert(meet != NULL);
    while (cur != meet)
    {
        cur = cur->next;
        meet = meet->next;
    }
    return cur;
}

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

这里写图片描述

思路:两条不带环的链表相交最后一个结点必然相同。

int IsCross(pLinkList plist1, pLinkList plist2)
{
    pNode end1 = plist1;
    pNode end2 = plist2;
    if ((plist1 == NULL) || (plist2 == NULL))
    {
        return 0;
    }
    //确定链表一的尾结点
    while (end1->next != NULL)
    {
        end1 = end1->next;
    }
    //确定链表二的尾结点
    while (end2->next != NULL)
    {
        end2 = end2->next;
    }
    return end1 == end2;
}

（15）.求两个不带环单链表的交点