单链表的插入删除以及逆转
一、背景说明

参加了某团购网站2014年的校招笔试，里面考到了一道单链表反转的题目。要求每隔k个元素反转一次。

如k=1时，链表1，2，3，4，5，6，7，8反转后为1，2，3，4，5，6，7，8

k=3时，链表1，2，3，4，5，6，7，8反转后为3，2，1，6，5，4，8，7

当时不会做，于是回来重新复习了下链表并实现了以下操作：

1）创建头结点

注意这里要把头结点L返回，因为传入的形参是头结点指针，给头结点分配空间后指针地址变化了。所以需要返回指针L才行。

（这里改变的不是指针指向的内容，而是指针的地址）

2）在位置i插入元素

找到要插入的位置i的前一个元素p。

创建一个新的结点s，s的后缀指针指向p的下一个。

p的后缀指针指向s。

3）删除位置i的元素

找到要删除的位置i的前一个元素p。

r为p的下一个元素，即要删除的元素。

p的后缀指针指向r的下一个元素。

释放r。

4）单链表反转

提示：假设有三个元素pPrev，pNode，pNext。要想反转pNode，pPrev，则把pNode的下一个指向pPrev就可以了。

但是此时链表就断开了，所以还需要记录下pNext的位置。不断循环直到链表尾（pNode为空）即可。

5）单链表每隔K个反转

提示：计算链表长度，除以反转间隔k得出要反转的趟数。参照4的方法反转即可。