C语言实现单链表面试题（基础篇）

顺序表和链表的优缺点

顺序表：
1. 内存中地址连续
2. 长度不可变更
3. 支持随机查找 可以在O(1)内查找元素
4.适用于需要大量访问元素的 而少量增添/删除元素的程序
链表 ：
1. 内存中地址非连续
2. 长度可以实时变化
3. 不支持随机查找 查找元素时间复杂度O（n）
4. 适用于需要进行大量增添/删除元素操作而对访问元素无要求的程序

在这里我们先定义一个单链表，下面进行对链表的操作。

typedef int DataType;

typedef struct ListNode
{
    DataType data;
    struct Node*next;
}Node,*pNode,*pList;//结点

从尾到头打印单链表

注意，这里是逆序打印链表，并不是逆序，不需要真正的改变链表的顺序，只需要打印就好。
思想：这里用一个递归实现逆序打印，一直递归，到最后一个，然后打印，返回上一层，这样就实现了逆序打印。具体代码如下。

void ReversePrint(pList plist)//逆序打印链表
{
    pNode cur = plist;

    if(plist==NULL)//链表为空
    {
        return;
    }
    if (plist->next==NULL)
    {
        printf ("%d ",plist->data);
        return;
    }
    ReversePrint(cur->next);//递归
    printf ("%d ",cur->data);

}

删除一个无头单链表的非尾节点

思想：删除无头单链表的非尾结点，也就是说不能删除尾，所以我们想到，肯定需要判断，为尾就不可以删除。具体实现代码如下：

void DelNotTailNode(pNode pos)
{
    pNode del = NULL;
    assert (pos->next!=NULL);
    del = pos->next;
    pos->data = pos->next->data;//把下一个数给前一个
    pos->next = pos->next->next;//让这个指针有能力指向下下一个
    free(del);//注意每次释放后把这个临时的结点置空，防止内存泄漏
    del = NULL;
}

在无头单链表的一个节点前插入一个节点

思想：因为是单链表，不能找到前一个，所以在结点前面插入，就需要换一种思想了。可以考虑把数据进行交换，具体代码如下

void InsertFrontNode(pNode pos,DataType d)//在指定位置的前面插入一个,非头
{
    DataType tmp = 0;
    pNode newnode = BuyNode(d);
    newnode->next = pos->next;//newnode指向的next有能力指向pos指向的next,就可以指向下一个
    pos->next = newnode;//pos有能力指向newnode
    tmp =pos->data;//交换两个数的值，就可以实现前加
    pos->data = pos->next->data;
    pos->next->data = tmp;

}

单链表实现约瑟夫环

约瑟夫环：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。约瑟夫环结束
那么用单链表实现，这个链表应该是环状的。

pNode JosephCircle(pList *pplist,int num)//约瑟夫环
{
    pNode cur = *pplist;
    pNode del = NULL;
    assert(pplist);
    while(1)
    {
        int count = num;
        if(cur == cur->next)//只有一个结点的环
        {
            break;
        }
        while(--count)//这个数结束后才会出列，没结束之前，一直向后走
        {
            cur = cur->next;

        }
        //走到这里就开始删除，然后继续循环  
        printf ("%d ",cur->data);
        del = cur->next;
        cur->data = cur->next->data;
        cur->next = cur->next->next;
        free(del);
        del = NULL;
    }
    return cur;
}

逆置单链表

这次才是逆置单链表，上面那个是逆序，只打印不改变，这个则是要改变链表。
思想：1. 考虑没有结点，则不需要逆置
2. 一个结点，也不需要逆置
3. 正常情况，就是改变定义的新的头结点，让它去改变这个链表，最后只需要把定义的那个头连上链表的头即可。代码如下。

void ReverseList(pList *pplist)//逆置
{
    pNode newHead = *pplist;
    pNode cur = NULL;
    pNode tmp = NULL;
    assert(pplist);
    if (*pplist==NULL)//为空则不需要逆置
    {
        return;
    }
    if ((*pplist)->next==NULL)//有个结点也不需要逆置
    {
        return;
    }
    cur = newHead->next;//cur指向第二个
    newHead->next = NULL;
    while(cur)
    {
        tmp =cur;
        cur = cur->next;
        tmp->next = newHead;//后一个有能力指向前一个
        newHead = tmp;
    }
    *pplist = newHead;//最后改变头结点就可以实现逆置

}

单链表排序（冒泡排序&快速排序）

void BubbleSort(pList *pplist)//冒泡排序,定义一个尾指针
{
    pNode cur = *pplist;
    pNode tail = NULL;
    assert(pplist);
    if (cur==NULL)//链表为空
    {
        return;
    }
    if (cur->next==NULL)//一个元素
    {
        return;
    }
    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;
                tail = NULL;
            }
            cur= cur->next;
        }
        tail = cur;
        cur = *pplist;
    }
}

合并两个有序链表,合并后依然有序

pList Merge(pList l1,pList l2)
{
    pNode cur1 = l1;
    pNode cur2 = l2;
    pNode newhead = NULL;
    pNode tail = NULL;
    if ((l1==NULL)&&(l2==NULL))//两个链表都为空
    {
        return NULL;
    }
    if(l1==NULL)//l1为空
    {
        return l2;
    }
    if (l2==NULL)//l2为空
    {
        return l1;
    }
        //下面是正常情况
        if(cur1->data<=cur2->data)
        {
            newhead = cur1;
            cur1 = cur1->next;
            tail = newhead;
            //tail->next = Merge(cur1,cur2);

        }
        else 
        {
            newhead = cur2;
            cur2 = cur2->next;
            tail = newhead;
            //tail->next = Merge(cur1,cur2);
        }
        while(cur1&&cur2)
        {
            if (cur1->datadata)
            {
                tail->next = cur1;
                cur1 = cur1->next;
                tail = tail->next;
            }
            else
            {
                tail->next = cur2;
                cur2= cur2->next;
                tail = tail->next;
            }
            if (cur1==NULL)//在这里判断一下，是否有某个链表已经为空了
            {
                tail->next = cur2;
            }
            if (cur2==NULL)
            {
                tail->next = cur1;
            }   
        }

    return newhead;
}

查找单链表的中间节点，要求只能遍历一次链表

pNode FindMidNode(pList plist)
{
    pNode fast = plist;      //运用快慢指针二倍的关系
    pNode slow = plist;
    if (plist==NULL)//链表空
    {
        return NULL;
    }
    while (fast&&(fast->next))//这里有两个条件，是因为链表元素个数的奇偶
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;//最后放回这个慢的
}

查找单链表的倒数第k个节点，要求只能遍历一次链表

思想：首先定义两个指针，一个指针比另一个先走k步，然后两个一起走，当快的那个走完，慢的指向的就是要找的那个。
代码如下

void FindKNode(pList *pplist,int k)//找链表的倒数第K个结点
{
    pNode fast = *pplist;
    pNode slow = *pplist;
    if(*pplist==NULL)//链表为空
    {
        return;
    }
    while (fast&&(fast->next))
    {
        fast = fast->next;
        if (--k<=0)//这里就是控制慢指针的
        {
            slow = slow->next;
        }
    }

        printf("%d\n",slow->data);

}

以上这些就是基础的单链表的面试题，后续还会写进阶版的。
观点是个人见解，如有错误，欢迎指正，谢谢。