单链表的面试题：

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

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

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

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

5从尾到头打印单链表

6逆置 / 反转单链表

---

存储结构：

typedef int DataType;

typedef struct SListNode

{

DataType _data;

struct SListNode*  _next;

}SListNode;

单链表的 增 删 查 在此省略

---

//替换法  pos  ——  pos->_next   //快慢指针 fast slow   //递归  

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

   1 --》 2 --》 3 --》 4 --》 5--》 NULL

              pos   del   next

void DelNoTailNode(SListNode* pos)  //替换法  {	assert(pos);	assert(pos->_next);	SListNode* del = pos->_next ;	SListNode* next = del->_next;	pos->_data = del->_data;	pos->_next = del->_next;    free(del);}

2.在无头单链表的一个非头节点前插入一个节点

   1 --》 2 --》 3 --》 5--》 NULL

                pos     next

                  tmp 4

1）void InsertFrontNode(SListNode* pos,DataType x)  {	assert(pos);	SListNode* tmp = _BuyNode(x);	tmp->_next = pos->_next;	pos->_next = tmp;	DataType tmpData = pos->_data;	pos->_data =tmp->_data;	tmp->_data = tmpData;  }  2）void InsertFrontNode(SListNode* pos,DataType x)    {	assert(pos);		SListNode* tmp = _BuyNode(pos->_data);  	tmp->_next = pos->_next;	pos->_next = tmp;	pos->_data = x; }

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

  fast一次走两步，slow一次走一步，直至fast至NULL

SListNode* FindMidNode(SListNode* pHead)  //快慢指针{	SListNode* fast = pHead;	SListNode* slow = pHead;	while (fast&&fast->_next)	{		fast = fast->_next->_next;		slow = slow->_next;	}	return slow;}//进一步思考//struct Ret{  SListNode* first;SListNode* second; };//奇数返回一个，偶数返回两个

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

 fast走k步，slow再走，至fast==NULL

SListNode* FindKNode(SListNode* pHead, DataType K)  //快慢指针{	SListNode* fast = pHead;	SListNode* slow = pHead;	while (fast&&K--)	{	         fast = fast->_next;	}	if (K > -1)  return NULL;	//if (fast == NULL) return NULL;	while (fast)	{		fast = fast->_next;		slow = slow->_next;	}	return slow;}

5.从尾到头打印单链表

void PrintTailToHead(SListNode* pHead)   //递归{	if (pHead)	{		PrintTailToHead(pHead->_next);		printf("%d->", pHead->_data);	}}

6.逆置 / 反转单链表

     1 --》 2 --》 3 --》 4 --》 NULL

 tmp,cur

               取节点tmp  newHead

             ... --》 1 --》 NULL

SListNode* Reverse(SListNode* pHead)   //取节点头插{	SListNode* cur = pHead;	//取节点，并置NULL	SListNode* newHead = NULL;	//头插	while (cur)	{		SListNode* tmp = cur;         cur = cur->_next;		tmp->_next = newHead;				newHead = tmp;	}	return newHead;}