【面试题】   单链表的热点面试题（1 ）

单链表的面试题：

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 --》 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; }

本文出自 “娜些维度的雪” 博客，请务必保留此出处http://1536262434.blog.51cto.com/10731069/1754122