一、比较顺序表和链表的优缺点，说说他们分别在什么场景下应用

空间上的比较（Space）

a. 空间的开辟：
顺序表的实现一般是实现连续开辟一段空间（或根据需求动态连续开辟空间），然后在进行数据的增删查改（静态顺序表），所以顺序表一般是固定空间大小的；
单链表则是一次只开辟一个结点的空间，用来存储当前要保存的数据及指向下一个结点或NULL的指针，所以单链表的空间大小时动态变化的。

b. 空间的使用：
当我们不知道要存储多少数据时，用顺序表来开辟的空间如果太大，就会造成一定程度上的浪费。
用单链表是实现时，因为是每需要存储一个数据时，才开辟一个空间，虽然有非数据项的指针占空间，但相比顺序表来说，浪费不是那么明显。(因为链表每次都是开辟的位置都是随机的，那么可能会把这块空间搞得七零八碎，出现很多小的一般使用不到的碎片空间)

c. 对CPU高速缓存的影响：
顺序表的空间一般是连续开辟的，而且一次会开辟存储多个元素的空间，所以在使用顺序表时，可以一次把多个数据写入高速缓存，再写入主存，顺序表的CPU高速缓存效率更高，且CPU流水线也不会总是被打断；
单链表是每需要存储一个数据才开辟一次空间，所以每个数据存储时都要单独的写入高速缓存区，再写入主存，这样就造成了，单链表CPU高速缓存效率低，且CPU流水线会经常被打断。

时间上的比较（Time）

a. 访问随机元素的时间复杂度：
顺序表访问随机元素的时间复杂度是O（1），而单链表访问随机元素的平均时间复杂度是O（n）。
b. 随机位置插入、删除元素的时间复杂度：
顺序表在插入随机位置插入、删除元素的平均时间复杂度是O（n），
单链表在插入随机位置插入、删除元素的时间复杂度是O（1）。

应用场景：

在查询操作使用的比较频繁时，使用顺序表会好一些；
在插入、删除操作使用的比较频繁时，使用单链表会好一些。

二、如何从头到尾打印单链表（使用递归的思想，我们便很容易有思路）

void PrintHeadtoTail(ListNode* plist)
{
    if(plist == NULL)
    {
        printf("NULL");
        return;
    }
    PrintHeadtoTail(plist->next);
    printf("<-%d",plist->data);
}

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

实现思路：无头单链表我们是无法找到非尾节点的前一个节点的，只能通过把目标节点的下一个节点的信息复制给自己，然后删除下个节点，达到删除自己的目的（即自己所报的信息不存在了）。

void EraseNonTail(ListNode* pos)//删除无头链表指定非尾节点
{
    if ((pos==NULL)&&(pos->next==NULL))
    {
        return;
    } 
    else
    {
        ListNode* sur = pos->next;
        pos->next = sur->next;
        pos->data = sur->data;
        free(sur);
        sur = NULL;
    }
}

四、非头节点前插入节点

    void AddNoHeadTail(ListNode*pos, DataType x)//非头节点前插入节点
{
    ListNode* tmp = NULL;
    assert(pos);

    tmp = BuyList(x);
    tmp->next = pos->next;
    pos->next = tmp;
    tmp->data = pos->data;
    pos->data = x;  
}

四、单链表实现约瑟夫环

ListNode* JosephRing(ListNode*list, DataType k)//单链表实现约瑟夫环
{
    ListNode* cur = list;
    ListNode* pos = list;
    if (list==NULL)
    {
        return NULL;
    }
    //首尾相连成环
    while(pos->next)
    {
        pos = pos->next;
    }
    pos->next = list;
    while (cur->next!=cur)//终止条件为只剩一个节点
    {
        DataType n = k;
        while (n--)
        {
            pos = cur;
            cur = cur->next;
        }
        pos->next = cur->next;
        free(cur);
        cur = pos->next;
    }
    return cur;
}

5.逆置、翻转单链表

ListNode* Reverse(ListNode* list)//逆置反转单链表
{
    ListNode* newhead = NULL;
    ListNode* pos = list;
    ListNode* cur = pos;
    while (cur)
    {
        pos = cur;
        cur = cur->next;
        pos->next = newhead;
        newhead = pos;
    }
    return newhead;
}

6.排序单链表

void Bubblesort(ListNode* list) //排序单链表
{
    ListNode* tail = NULL;
    ListNode* next = NULL;
    ListNode* pos = NULL;

    if ((list==NULL)||(list->next == NULL))
    {
        return;
    }

    while (list->next != tail)
    {
        pos = list;
        next = pos->next;

        while (tail != next)
        {
            if (pos->data > next->data)
            {
                DataType tmp = pos->data;
                pos->data = next->data;
                next->data = tmp;
            }
            pos = pos->next;
            next = next->next;          
        }
        tail = pos;
    }
}

7.合并有序单链表，合并后依然有序

ListNode* Conbine(ListNode* list1, ListNode* list2)
{
    ListNode* head = NULL;
    ListNode* tail = NULL;

    if (list1 == NULL)
    {
        return list2;
    }   
    if (list2 == NULL)
    {
        return list1;
    }
    //先找出两个链表中的一个小的节点，把他摘下来做新链表的头结点
    if(list1->data > list2->data)
    {
        head = list2;
        list2 = list2->next;
    }
    else
    {
        head = list1;
        list1 = list1->next;
    }
    tail = head;

    while (list1 && list2)
    {
        if (list1->data > list2->data)
        {
            tail->next = list2;
            list2 = list2->next;    
        } 
        else
        {
            tail->next = list1;
            list1 = list1->next;
        }
        tail = tail->next;
    }
    if (list1 == NULL)
    {
        tail->next = list2;
    } 
    else 
    {
        tail->next = list1;
    }
    return head;    
}

8.查找单链中间节点（只遍历一次链表）

ListNode* FindMidTail(ListNode* list)
{
    ListNode* fast = list;
    ListNode* slow = NULL;

    while ((fast!=NULL)&&(fast->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;    
}

9.查找单链表中的倒数第k个节点

ListNode* FindTail_k_Node(ListNode* list, int k)
{
    ListNode* fast = list;
    ListNode* slow = list;

    while (--k)
    {
        if(fast == NULL)//说明k的值大于链长
        {
            return NULL;
        }
        fast = fast->next;
    }

    while (fast->next)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

10.判断一个链表是否带环，若带环求环入口点，环长

//判断是否带环,带环返回入口点，不带环返回空
ListNode* JudgeLoop(ListNode* list)
{
    ListNode* fast = list;
    ListNode* slow = list;

    while (fast && fast->next)
    {
        slow = slow->next;          
        fast = fast->next->next;
        if (fast == slow)
        {
            //printf("该单链表有环\n");
            return fast;
        }
    }
    //printf("该链表无环\n");
    return NULL;
}

ListNode* GetCyclen(ListNode* list)//若带环求环的节点环长
{
    ListNode* meetnode = JudgeLoop(list); 
    ListNode* fast = NULL;
    ListNode* slow = NULL;
    ListNode* loopnode = NULL;//环内相遇点   
    ListNode* listnode = NULL;
    int count = 1;//声明计数器，记录环长

    if (meetnode == NULL)
    {
        return NULL;
    }

    fast = meetnode->next->next;
    slow = meetnode->next;
    listnode = list;//起始点
    loopnode = meetnode;//环内相遇点 

    while (fast != slow)
    {
        fast = fast->next->next;
        slow = slow->next;
        count++;
    }
    printf("环长为：%d\n", count);
    while (listnode != loopnode)
    {
        listnode = listnode->next;
        loopnode = loopnode->next;
    }
    printf("环的入口点为：%d\n", loopnode->data);
    return loopnode; //环的入口点
}

11.判断两条链表是否相交，若相交返回相交点（假设不带环）

//判断两个链表是否相交,假设不带环（链表长度相减法）
ListNode* CheckIsMeet(ListNode* plist1, ListNode* plist2)
{
    int len1 = 0;
    int len2 = 0;
    int len = 0;
    ListNode* pos1 = plist1;
    ListNode* pos2 = plist2;

    if ((plist1 == NULL)||(plist2 == NULL))
    {
        return NULL;
    }

    while (pos1->next)
    {
        pos1 = pos1->next;
        len1++;
    }
    while (pos2->next)
    {
        pos2 = pos2->next;
        len2++;
    }

    len =len1 - len2;

    pos1 = plist1;
    pos2 = plist2;
    if(len>0)
    {   
        while (len--)
        {
            pos1 = pos1->next;
        }
    }
    else
    {
        len = abs(len); //对len求绝对值
        while (len--)
        {
            pos2 = pos2->next;
        }
    }
    while (pos1)
    {
        if (pos1 == pos2)
        {
            return pos1;
        }
        pos1 = pos1->next;
        pos2 = pos2->next;
    }
    return NULL;
}

12.链表相交问题升级版（可能带环）

//判断链表是否相交（可能带环）
ListNode* CheckMeet_All(ListNode* list1, ListNode* list2)
{
    ListNode *cur1 = JudgeLoop(list1);
    ListNode *cur2 = JudgeLoop(list2);

    ListNode *ent1 = NULL;
    //1.两个链表都不带环
    if ((cur1 == NULL) && (cur2 == NULL))
    {
        return CheckIsMeet(list1, list2); 
    }
    //2.一个带环，一个不带环(不可能相交)
    else if (((cur1==NULL)&&(cur2!=NULL))||((cur1!=NULL)&&(cur2==NULL)))
    {
        return NULL;
    }
    //3.两个链表都带环，分两种情况
    else
    {   
        //1.入口点相同则尾交,去掉环转换成不带环链表相交问题
        if (cur1 == cur2)
        {       
            cur1->next = NULL;
            return CheckIsMeet(list1,list2);
        }
        //2.同环两个入口点
        //让一个入口点遍历一遍看是否有另一个入口点
        else 
        {
            ent1 = cur1->next;
            while(ent1 != cur1)
            {
                if (ent1 == cur2)
                {
                    return ent1;
                }
            ent1 = ent1->next;
            }           
            return NULL;
        }       
    }
}