单链表的面试题

单链表的面试题
基本的单链表的实现在之前博客中

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__
typedef int DataType;

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct Node
{
    DataType _data;//单链表的数据域
struct Node* _next;//单链表的指针域
}Node,*pNode, *pList;
void InitLinkList(pList *pplist);//初始化单链表
void PushBack(pList *pplist, DataType x);//c从尾部向单链表中插入元素
void Display(pList plist);//输出函数
void Destory(pList* pplist);//销毁单链表，释放空间

这几个函数的功能实现在之前博客中已经说过，这里不再赘述；

上述形成的单链表如下：

//对所有元素进行排序
void Bubblesort(pList *pplist);
//逆置单链表
void ReversePrint(pList plist);
//删除无头单链表的非尾结点
void EraseNotTail(pNode pos);
//在无头单链表的非头结点前插入一个元素
void InsertFrontNode(pNode pos,DataType x);
//约瑟夫环的问题
void  JosephCycle(pList *pplist,int k);
//逆序单项链表
void ReverseList(pList *pplist);

面试题中常见的单链表

//对单链表中所有的元素进行冒泡功能的实现
基本的实现思路是

void BubbleSort(pList *pplist)
{
    pNode tail = NULL;
    pNode pre = NULL;//定义两个指针-->后指针
    pNode cur = NULL;//前指针
    DataType tmp;
while (tail != (*pplist)->_next)
    {
        pre = *pplist;
        cur = pre->_next;
while ((cur != tail) && (pre->_next != tail))
        {
if ((cur->_data) > (pre->_data))//交换前后两个结点的值
            {
                tmp = cur->_data;
                cur->_data = pre->_data;
                pre->_data = tmp;
            }
            pre = pre->_next;
if (cur->_next != tail)//这里必须要注意，cur移动到tail的前一个时不需要移动，这里注意下条件
            {
                cur = cur->_next;
            }
        }
        tail = cur;
    }
}

结果是

//逆序打印单链表
基本的思路是：递归

void ReversePrint(pList plist)//逆序打印单链表
{
    assert(plist);
    pNode cur = plist;
if (cur != NULL)//判断第一个结点是不是为空
    {
if (cur->_next!=NULL)//递归的条件是cur的next不为空，也就是到最后一个元素，不需要递归
        {
            ReversePrint(cur->_next);
        }
        printf("%d->", cur->_data);
    }
return;
}

显示的结果是

//删除无头单链表的非尾结点
基本的实现思路是：让当前这个结点的值与它的下一个结点的值进行交换，然后删除下一个结点，就相当于删除了当前结点。

void EraseNotTail(pNode pos)
{
    pNode del = NULL;
    assert(pos);
    DataType tmp;
    tmp = pos->_data;
    pos->_data = pos->_next->_data;
    pos->_next->_data = tmp;
    del = pos->_next;
    pos->_next = pos->_next->_next;
    free(del);
}

//显示的结果是

//在无头单链表的非头结点前插入一个元素
基本的思路是：相当与在后面插入元素，然后交换元素的值即可。

void InsertFrontNode(pNode pos, DataType x)
{
    DataType tmp;
    assert(pos);
    pNode newnode = BuyNode(x);
    newnode->_next = pos->_next;
    pos->_next = newnode;
    tmp = pos->_data;
    pos->_data = newnode->_data;
    newnode->_data = tmp;
}

//显示的结果是

//约瑟夫环的问题
设计的思路是:这是一个非常典型的例子，约瑟夫当年就是因为这个而与他的朋友活了下来。如果假设现在每3个人死一个的话，在一个环形链表中，每3个结点，删除一个结点，循环终止的条件就是自己等于自己。

void  JosephCycle(pList *pplist, int k)
{
    pNode cur = NULL;
    int i = 0;
    pNode del = NULL;
    assert(pplist);
    cur = *pplist;//从第一个元素开始往后数
while (cur->_next != cur)
    {
        for (i = 0; i < k - 1; i++)
        {
            cur = cur->_next;//先移动到当前所要删除的元素的位置
        }
if (cur->_next != NULL)
        {
            EraseNotTail(cur);//根据前面所说的无头结点的删法删除
        }   
    }
    printf("%d\n", cur->_data);//打印最后没有被删的元素的值
}

//显示结果是

//逆序单项链表
基本思路：把单链表之后的结点一个个往前插

void ReverseList(pList *pplist)
{
    pNode cur = NULL;
    pNode prev = NULL;
    pNode p = NULL;
    assert(pplist);
    cur = *pplist;
if (*pplist == NULL)
    {
return;
    }
    cur = (*pplist)->_next;
    (*pplist)->_next = NULL;
while (cur->_next != NULL)
    {
        prev = cur;//保存当前的值
        cur = cur->_next;//让指针移动到下一个位置
        p = prev;//再赋给另一个指针，不然之后的元素找不到
        p->_next = *pplist;//删除
*pplist = p;
    }
    cur->_next = *pplist;//插入最后一个元素
*pplist = cur;
}

//显示的结果是

//查找单链表的中间节点，要求只能遍历一遍单链表
基本思路：定义快指针和慢指针，让快指针为 慢指针的2倍，当快指针到最后时，慢指针就到了中间结点。

//查找单链表的中间节点，要求只能遍历一遍单链表
pNode FindMidNode(pList plist)
{
    pNode cur = NULL;//定义一个快指针和慢指针
    pNode pre = NULL;
    assert(plist);
    cur = plist;
if (plist == NULL)//如果没有结点，则返回
    {
return;
    }
while (cur->_next != NULL)
    {
        pre = cur;//让快指针等于慢指针的二倍
        cur = cur->_next->_next;
    }
return pre;//返回慢指针就是中间结点
}

下面几个函数给出一个结果
//查找单链表的倒数第k个节点，要求只能遍历一次链表
基本思路：让一个指针先走k步，然后两个指针一起走，当快的这个指针为空时，慢指针就到了倒数第k个结点

pNode FingKNode(pList plist, int k)
{
    pNode cur = NULL;//定义一个快指针和慢指针
    pNode pre = NULL;
    assert(plist);
    cur = plist;
    pre = plist;
    int i = 0;
for (i = 0; i < k - 1; i++)
    {
        cur = cur->_next;
    }
while (cur->_next != NULL)
    {
        pre = pre->_next;
        cur = cur->_next;
    }
return pre;
}

//判断链表是不是带环
基本思路是：还是像之前一样，定义快慢指针，让快指针的速度是慢指针的2倍，如果链表带环，就一定会相遇。

pNode CheckCircle(pList plist)
{
    pNode fast = NULL;//定义一个快指针和慢指针
    pNode slow = NULL;
    assert(plist);
    fast = plist;
    slow = plist;
while ((fast) && (fast->_next != NULL))//不能只有一个元素。不能没有结点，不能到最后一个元素
    {
        slow = slow->_next;//慢指针走一步，快指针走两步
        fast = fast->_next->_next;
if (fast == slow)
        {
return fast;
        }
    }
return NULL;
}

//求环的长度
基本思路：之前判断链表是不是带环的时候判断出了相遇点，从相遇点开始计时器加加，知道等于相遇点，则就是环的长度

int GetCycleLength(pNode meet)
{
    pNode cur = NULL;
    assert(meet);
    cur = meet;
int count = 0;
    do
    {
        cur = cur->_next;
count++;
    } while (cur != meet);
return count;
}

//求环的入口点

pNode GetCycleEntryNode(pList plist, pNode meet)
{
    pNode p1 = NULL;
    pNode p2 = NULL;
    assert(plist);
    assert(meet);
    p1 = plist;
    p2 = meet;
while (p1 != p2)
    {
        p1 = p1->_next;
        p2 = p2->_next;
    }
return p1;
}

//合并两个有序列表
基本思路：把第二个链表的元素一个个往里插，插的时候注意比较元素的值，第一个链表为空时直接将元素赋进去。考虑链表不能为空，一个元素相等的情况。

pList Merge(const pList *p1,  pList *p2)
{
    pNode first = NULL;
    pNode second = NULL;
    pNode cur = NULL;
    pNode cur2 = NULL;
    assert(p1);
    assert(p2);
    first =*p1;
    second =*p2;
if (((*p1) == (*p2)) || (*p1 == NULL) || (*p2==NULL))
    {
return NULL;//如果两个链表都为空，或者有一个为空返回
    }
while (second->_next!=NULL) //插入的链表不能为空，为空停止
    {
while ((first->_data) < (second->_data))//比较两个链表的元素
        {
if (first->_next != NULL)
            {
                cur = first;//保存前一个结点，为以后插入式使用
                first = first->_next;
            }
else
            {
                break;//如果被插的那条链表为空，直接跳出去插入剩下的元素
            }   
        }
        cur2 = second;//保存要插入的元素
*p2 = (*p2)->_next;//链表二向后移动
        second = *p2;
        cur2->_next = first;
        cur->_next = cur2;
    }
    first->_next = *p2;//跳出来之后直接把剩下的元素加上去
return *p1;
}

显示结果

//判断两条单项链表是否相交
基本的思路是：让第一条链表的位和第二个链表的头连起来。判断是不是带环，如果带环，则就相交

int CheckCross(pList list1, pList list2)
{
    pNode p1 = NULL;
    pNode p2 = NULL;
    pNode ret;
    assert(list1);
    assert(list2);
    p1 = list1;
while (p1->_next != NULL)
    {
        p1 = p1->_next;
    }
    p1->_next = list2;//将两条链表连接
    ret = CheckCircle(list1);//判断带环
if (ret != NULL)
    {
return 1;
    }
else
    {
return 0;
    }
}

//求交点
如果相交，就是求入口点的问题，上同

pNode GetCrossNode(pList list1, pList list2)
{
    pNode p1 = NULL;
    pNode p2 = NULL;
    pNode ret;
    pNode ret1;
    assert(list1);
    assert(list2);
    p1 = list1;
while (p1->_next != NULL)
    {
        p1 = p1->_next;
    }
    p1->_next = list2;//先把两个链表连成环
    ret = CheckCircle(list1);//链表带环的相遇点
    ret1=GetCycleEntryNode(list1, ret);
return ret1;
}

显示的结果是：

下面是头文件和测试函数
头文件

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__
typedef int DataType;

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct Node
{
    DataType _data;//单链表的数据域
struct Node* _next;//单链表的指针域
}Node,*pNode, *pList;
void InitLinkList(pList *pplist);//初始化单链表
void PushBack(pList *pplist, DataType x);//c从尾部向单链表中插入元素
void Display(pList plist);//输出函数
//C链表的面试题
//逆置单链表
void ReversePrint(pList plist);
//删除无头单链表的非尾结点
void EraseNotTail(pNode pos);
//在无头单链表的非头结点前插入一个元素
void InsertFrontNode(pNode pos,DataType x);
//约瑟夫环的问题
void  JosephCycle(pList *pplist,int k);
//逆序单项链表
void ReverseList(pList *pplist);
//合并两个有序列表
pList Merge(const pList *p1, const pList *p2);
//查找单链表的中间节点，要求只能遍历一遍单链表
pNode FindMidNode(pList plist);
//查找单链表的倒数第k个节点，要求只能遍历一次链表
pNode FingKNode(pList plist,int k);
//判断链表是不是带环
pNode CheckCircle(pList plist);
//求环的长度
int GetCycleLength(pNode meet);
//求环的入口点
pNode GetCycleEntryNode(pList plist, pNode meet);
//判断两条单项链表是否相交
int CheckCross(pList list1, pList list2);
//求交点
pNode GetCrossNode(pList list1, pList list2);
#endif __LINK_LIST_H__

测试函数

void test1()
{
    pList plist;//指针类型的变量
    pNode ret;
    pNode p;
    pNode m;
int k;
    pNode ret2;

    InitLinkList(&plist);//初始化单链表
    PushBack(&plist, 1);//c从尾部向单链表中插入元素
    PushBack(&plist, 4);
    PushBack(&plist, 5);
    PushBack(&plist, 7);
    PushBack(&plist, 9);
    Display(plist);
    BubbleSort(&plist);
    Display(plist);
    ReversePrint(plist);//逆置单链表
printf("\n");
    ret = Find(plist, 5);
    EraseNotTail(ret);//删除无头单链表的非尾结点
    Display(plist);
    ret = Find(plist,7);
    InsertFrontNode(ret, 6);
    Display(plist);
    ReverseList(&plist);
    Display(plist);
    ret = FindMidNode(plist);//找中间结点
printf("中间结点是：%d\n", ret->_data);
    ret = FingKNode(plist, 2);//找倒数第k个结点
printf("找到的倒数第k个结点是：%d\n", ret->_data);
    m = Find(plist, 7);
    p = Find(plist,9);
    p->_next = m;
    ret=CheckCircle(plist);//判断是不是带环
printf("相遇的点是：%d\n", ret->_data);
if (ret!=NULL)
    {
printf("带环\n");
        k = GetCycleLength(ret);//判断环的长度
printf("环的长度是：%d\n",k);
        ret2=GetCycleEntryNode(plist, ret);//环入口点
printf("环的入口点是：%d\n",ret2->_data);

    }
else
    {
printf("不带环\n");
    }
//ret = Find(plist, 9);
//ret->_next = plist;
//JosephCycle(&plist, 3);
//Destory(&plist);
}
void test2()
{
    pList plist1;
    pList plist2;
    pNode ret;
    InitLinkList(&plist1);//初始化
    InitLinkList(&plist2);
    PushBack(&plist1, 1);//插入元素
    PushBack(&plist1, 3);
    PushBack(&plist1, 5);
    PushBack(&plist1, 7);
    PushBack(&plist2, 2);
    PushBack(&plist2, 4);
    PushBack(&plist2, 6);
    PushBack(&plist2, 8);
    Display(plist1);
    Display(plist2);
    ret=Merge(&plist1, &plist2);//合并两条链表
    Display(ret);

}
test3()
{
    pList plist1;
    pList plist2;
    pNode ret;
int k;
    pNode m;
    pNode n;
    InitLinkList(&plist1);
    InitLinkList(&plist2);
    PushBack(&plist1, 1);
    PushBack(&plist1, 3);
    PushBack(&plist1, 5);
    PushBack(&plist1, 7);
    PushBack(&plist1, 9);
    PushBack(&plist1, 11);
    PushBack(&plist2, 2);
    PushBack(&plist2, 4);
    PushBack(&plist2, 6);
    Display(plist1);
    Display(plist2);
    m = Find(plist2, 6);
    n = Find(plist1,7);
    m->_next = n;
//ret = GetCrossNode(plist1, plist2);
//printf("%d\n", ret->_data);
    k=CheckCross(plist1, plist2);//判断链表是不是带环
if (k)
    {
printf("两条单链表相交\n");
        ret = GetCrossNode(plist1, plist2);//环的交点
printf("交点是：%d\n", ret->_data);
    }
else
    {
printf("两条单链表不相交\n");
    }
}
int  main()
{
//test();
//test1();
//test2();
    test3();
return 0;
}