【面接問題】単鎖表のホットスポット試験問題(1)

単一チェーンテーブルの面接問題:
1ヘッダレス単一チェーンテーブルの非末尾ノードを削除
2ヘッダレス単一チェーンテーブルの非ヘッダノードの前にノードを挿入する
3単一チェーンテーブルの中間ノードを検索し、チェーンテーブルを1回だけ巡回する必要がある
4単一チェーンテーブルの最後からk番目のノードを検索し、チェーンテーブルを1回しか巡回できないことを要求する
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は1回に2歩、slowは1回に1歩、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番目のノードを検索し、チェーンテーブルを1回しか巡回できないことを要求する
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;
}