第1关：查找倒数第k个数

思路分析

遍历一遍统计一共有多少个节点，由于p=L->next,从第一个节点开始寻找，所以计算器cnt初始化为1，如果还有后续节点，我们就继续查找，然后L重新回到L->next（第一个节点），然后进行查找，当节点数达到 i ==cnt-k+1则说明找到了，返回p即可。

代码展示

第2关：链表逆置

思路分析

原理非常简单，即把下一个节点的next指向当前节点，即p->next=pre,其中pre保存前一节点，p是当前节点。

代码展示

第3关：有序单链表的就地合并

代码展示

第4关：两个一元多项式异地相加

代码展示

第5关：约瑟夫环问题

代码展示

今日总结

• 1链表遍历是非常非常参见的，必须掌握。

• 2链表的长度未知时，我们可以先遍历链表，同时计数，就可以知道链表的长度了，在删除倒数第k个数中非常能够体现。

• 3链表反转的时候只需要记忆当前节点和前一个节点，进行反抓即可，需要注意的是pre初始化应该是NULL，因为反转后是链表末尾。最后链表L->next=pre是把链表头指向pre。

• 4多项式的合并这一题主要是和顺序表差不多，注意这一题要求答案存储在C中，并且A，B不改变，所以每次插入一个节点到C中都不能直接使用A，B中的节点，需要我们new一个新的节点，保持A，B链表的原样。

• 约瑟夫环是一个经典问题，网络上也有很多解答，这里就不重点介绍了，需要掌握循环链表的创建和单链表的遍历即可。