基础链表题

1.总结顺序表和链表的优缺点，说说它们分别在什么场景下使用？

2.从头到尾打印单链表
这个问题才用递归思想，设置一个边界条件，对函数本身进行调用，当满足边界条件时，递归返回，进行链表元素的打印。

void Start_to_End(ListNode *pList)
{
    ListNode *cur = pList;
    if (pList == NULL)
    {
        return;
    }
        Start_to_End(cur->next);//访问到最后一个元素时停止
        printf("%d ", cur->data);
}

3.删除一个无头单链表的非尾节点
因为此单链表不知道头节点的地址，所以找不到要删除节点的前一个节点，因此就可以即问题转化为：
1>,记录下pos的下一个节点；
2>,将pos下一个节点prev的数据赋给pos节点；
3>,让pos的下一个节点指向prev的下一个节点；
4>,最后free掉prev即可。

void Delete_NonHead(ListNode *pos)
{
    assert(pos&&pos->next);
    ListNode *prev = pos->next;
    pos->data = prev->data;
    pos->next = prev->next;
    free(prev);
}

4.在无头单链表的一个非头节点前插入一个节点
这个问题也是无头单链表，不能找到pos节点的前一个节点，所以pos的下一个节点是入口点，具体有以下两种方法：
第一种：1>,记录pos的下一个节点位置next；
2>,在pos节点的后面建立一个新的节点，改变指针的指向关系；
3>,建立一个临时变量，将pos的data和新建节点的data交换；

void Insert_Front_Node(ListNode *pos, DataType x)
{
    assert(pos);
    ListNode *prev = NewListNode(x);
    ListNode *next = pos->next;
    pos->next = prev;
    prev->next = next;
    int tmp = pos->data;
    pos->data = prev->data;
    prev->data = tmp;
}

第二种：1>,记录pos的下一个节点next；
2>,在pos节点的后面创建新节点，data为pos的data，将pos的data置为要插入新建节点的data；
3>, 改变指针的指向关系。

void Insert_Front_Node(ListNode *pos, DataType x)
{
    assert(pos);
    ListNode *next = pos->next;
    ListNode *prev = NewListNode(pos->data);
    pos->data = x;
    pos->next = prev;
    prev->next = next;
}

5.单链表实现约瑟夫环
先介绍一下约瑟夫环：一群人坐在一起围成一个环状，由任意一个人报数，数到某个数的时候，此人出列，下一个人重新报数，一直循环，直至所有人都出列。
当只剩一人的时候为终止条件，指定第k个人出列。

ListNode* Joseph(ListNode *hum, size_t k)
{
    assert(hum);
    ListNode *man = hum;
    while (man->next == man)
    {
        while (--k)
        {
            man = man->next;
        }
        ListNode *next = man->next;
        man->data = next->data;
        man->next = next->next;
        free(next);
    }
    return man;
}

6.逆置/反转单链表
开辟一个NULL节点，将原链表从头节点开始依次链到新建NULL节点后。

ListNode* Reverse_List(ListNode **ppList)
{
    ListNode *start = *ppList;  
    ListNode *newlist = NULL;
    while (start)
    {
        ListNode *cur = start->next;
        start->next = newlist;
        newlist = start;
        start = cur;
        *ppList = newlist;
    }
    return newlist;
}

7.单链表排序—–冒泡排序

void Bubble(ListNode *pList)
{
    ListNode* tail = NULL;
    if (pList == NULL || pList->next == NULL)
    {
        return;
    }
    while (tail != pList->next)
    {
        int flag = 0;
        ListNode *start = pList;
        ListNode *next = start->next;
        while (next != tail)
        {
            if (start->data > next->data)
            {
                flag = 1;
                DataType ret = start->data;
                start->data = next->data;
                next->data = ret;
            }
            start = start->next;
            next = next->next;
        }
        if (flag == 0)
        {
            break;
        }
        tail = start;
    }
}

8.合并两个有序链表, 合并后依然有序
1>,当list1为NULL时，返回list2;当list2为NULL时，返回list2;
2>,都不为空时，依次进行比较，如果节点的值小，就将该节点链到list上并指向下一个节点，data大的节点不变，遇到相等data时，任选一个节点链到list上；
3>,当有链表为空后，将另一个链表的值直接链到list上，返回list。

ListNode* Merge_list(ListNode* List1, ListNode* List2)
{
    if (List1 == NULL)
    {
        return List2;
    }
    if (List2 == NULL)
    {
        return List1;
    }
    ListNode* List = NULL;
    ListNode* tail = NULL;
    if (List1->data < List2->data)
    {
        List = List1;
        List1 = List1->next;
    }
    else if (List1->data>List2->data)
    {
        List = List2;
        List2 = List2->next;
    }
    tail = List;
    while (List1&&List2)
    {
        if (List1->data <= List2->data)
        {
            tail->next = List1;
            List1 = List1->next;
        }
        else
        {
            tail->next = List2;
            List2 = List2->next;
        }
        tail = tail->next;   //用tail遍历
        if (List1 == NULL)
        {
            tail->next = List2;
        }
        else if (List2 == NULL)
        {
            tail->next = List1;
        }
    }
    return List;
}

9.查找单链表的中间节点，要求只能遍历一次链表
这个问题要使用快慢指针来实现，定义一个fast指针，slow指针，slow指针每次走一步，而fast指针每次走两步，当fast指针走到尾时，slow指针刚好走到中间节点。

ListNode* Find_MidHead(ListNode* pList)
{
    ListNode* slow = pList;
    ListNode* fast = pList;
    while (fast && fast->next && fast->next->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

10.查找单链表的倒数第k个节点，要求只能遍历一次链表
定义fast指针和slow指针，fast一次走k-1步，slow一次走一步。

ListNode* Find_KHead(ListNode* pList, size_t k)
{
    ListNode* slow = pList;
    ListNode* fast = pList;
    while (--k)
    {
        if (fast == NULL)
        {
            return NULL;
        }
        else
        {
            fast = fast->next;
        }
    }
    while (fast->next)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}