【练习】链表面试题（二）基础

巩固一下基础，我重新写了一下无头节点单链表及链表面试题。我会分为入门，基础，进阶三章进行总结，点击以下蓝色字直接跳转对应章节。

链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶

链表头文件与基本实现在链表及链表面试题（一）入门中，此处不再赘述。

• 从尾到头打印单链表

//不改变链表结构，从尾到头打印单链表 （递归实现）
void PrintListRevers_Recursively(pList phead)
{
    if (phead)
    {
        if (phead->next)
        {
            PrintListRevers_Recursively(phead->next);
        }
        printf("%d ", phead->data);
    }
}

当链表非常长的时候，递归实现的会导致函数调用层级很深，可能导致调用栈溢出。用栈不会出现此类情况，显然用栈实现代码的鲁棒性会好一些。

//不改变链表结构，从尾到头打印单链表（栈实现） 
void PrintListRevers_Stack(pList phead)
{
    stack<pNode>nodes;

    pNode cur = phead;
    while (cur)
    {
        nodes.push(cur);
        cur = cur->next;
    }

    while (!nodes.empty())
    {
        cur = nodes.top();
        printf("%d ", cur->data);
        nodes.pop();
    }
}

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

void DeleteNotTailNode(pNode pos)
{
    if (pos == NULL)
        return;
    pNode tmp = pos->next;
    pos->data = tmp->data;
    pos->next = tmp->next;
    free(tmp);
    tmp = NULL;
}

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

void InsertNotHeadNode(pNode pos, DataType d)
{
    assert(pos);
    pNode tmp = BuyNode(pos->data);

    tmp->next = pos->next;
    pos->next = tmp;
    pos->data = d;

}

• 单链表实现约瑟夫环

//单链表实现约瑟夫环
pNode Joseph(pList plist, const int x)//默认从第一个开始，所以只传两个值
{
    pNode cur = plist;
    pNode head = plist;
    pNode prev = NULL;

    if (plist == NULL || x <= 0)
        return NULL;

    while (cur->next) // 成环
        cur = cur->next;
    cur->next = head;
    cur = cur->next;

    while (cur != cur->next)
    {
        int count = x;

        while (count--)
        {
            prev = cur;
            cur = cur->next;
        }
        prev->next = cur->next;
        prev->data = cur->data;
        free(cur);
        cur == NULL;
        cur = prev;
    }
    return cur;
}

• 逆置/反转单链表

//逆置链表
void ReverseList(pList* pplist)
{
    assert(pplist);
    pNode cur = *pplist;
    pNode newhead = *pplist;

    if (cur == NULL || cur->next == NULL)
        return;
    

    while (cur->next)
    {
        pNode tmp = cur->next;
        cur->next = tmp->next;
        tmp->next = newhead;
        newhead = tmp;
    }   
    *pplist = newhead;
}

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

常用排序算法时间复杂度和空间复杂度

冒泡排序的最坏时间复杂度为O(n^2)

//冒泡排序
void BubbleSort(pList* pplist)
{
    assert(pplist);
    pNode p = NULL;
    pNode q = NULL;

    for (p = *pplist; p != NULL; p = p->next)
    {
        for (q = p->next; q != NULL; q = q->next)
        {
            if (p->data > q->data)
            {
                DataType tmp;
                tmp = p->data;
                p->data = q->data;
                q->data = tmp;
            }
        }
    }
}

快速排序是在实际中最常用的一种排序算法，速度快，效率高。就像名字一样，快速排序是最优秀的一种排序算法。
** 快速排序采用的思想是分治思想。**

1. 先从数列中取出一个数作为基准数。
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3. 再对左右区间重复第二步，直到各区间只有一个数。
   尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。

//快速排序
void Quicksort(pNode begin, pNode end)
{
    if (begin == NULL || end == NULL)
        return;

    DataType K = begin->data;
    pNode slow = begin;
    pNode fast = begin->next;
        
    if (begin != end)
    {
        while (fast != NULL)
        {
            if (fast->data < K)
            {
                slow = slow->next;

                DataType tmp = fast->data;
                fast->data = slow->data;
                slow->data = tmp;
            }
            fast = fast->next;
        }
        DataType tmp1 = slow->data;
        slow->data = begin->data;
        begin->data = tmp1;

        Quicksort(begin, slow);
        Quicksort(slow->next, end);
    }
}

选择排序的最坏时间复杂度为O(n^2)。
两个元素一个走外层pNode out一个走内层pNode in，内层元素与外层元素比较大小。内层先遍历，如果升序排列，遇到小的元素则将小的的值交换到外层元素，内层走完一遍后，最小的已经在最前面了，然后外层走向下一个元素，内层继续从外层的下一个元素开始遍历重复之前动作，直至外层也遍历完成，整个排序结束。选择排序是** 不稳定的排序 **方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

//选择排序
void SelectionSort(pList plist)
{
    assert(plist);
    pNode out= plist;
    pNode in = NULL;

    for (; out!= NULL; out = out->next)
    {
        for (in = out->next; in != NULL; in = in ->next)
        {
            if (out->data > in ->data)
            {
                DataType tmp = out->data;
                out->data = in->data;
                in->data = tmp;
            }
        }
    }
}

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

pList Merge(pList list1, pList list2)
{
    if (list1 == NULL)//返回条件
        return list2; 
    if (list2 == NULL)//返回条件
        return list1; 

    pList newlist = NULL;

    if (list1->data < list2->data)
    {
        newlist = list1;
        newlist->next = Merge(list1->next, list2); // 递归
    }
    else 
    {
        newlist = list2;
        newlist->next = Merge(list1, list2->next); // 递归
    }
    return newlist;
}

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

pNode FindMiddleNode(pList list)
{
    if (list == NULL)
        return NULL;

    pNode fast = list;
    pNode slow = list;

    while (fast && fast->next) //判断顺序不能颠倒
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

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

//FindKthToTail
pNode FindKthToTail(pList list, unsigned int k)
{
    if (list == NULL || k == 0) //注意鲁棒性，容易忽略(参数检查)
        return NULL;

    pNode prev = list;
    pNode cur = NULL;
    
    for (unsigned int i = 0; i < k - 1; ++i)
    {
        if (prev->next != NULL)
            prev = prev->next;
        else
            return NULL;    //注意鲁棒性，容易忽略(节点个数小于k)
    }

    cur = list;
    while (prev->next)
    {
        prev = prev->next;
        cur = cur->next;
    }
    return cur;
}

//test find middle/find k
void testFind()
{
    pList plist;
    InitList(&plist);

    PushBack(&plist, 1);
    PushBack(&plist, 2);
    PushBack(&plist, 3);
    PushBack(&plist, 4);
    PushBack(&plist, 5);
    PushBack(&plist, 6);
    PrintList(plist);

    //printf("%d \n", FindMiddleNode(NULL)->data);
    printf("%d \n", FindMiddleNode(plist)->data);

    for (int i = -1; i < 7; ++i)
    {
        pNode ret = FindKthToTail(plist, i);
        if (ret)
            printf("%d ", ret->data);
    }
    printf("\n");
}

链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶