【100題】チェーンテーブルの最後からk番目の要素を探し出す

// k 
#include <iostream>
using namespace std;
// 
struct ListNode
{
	 int data;
	 ListNode *next;
};
// 
void createList(ListNode *&Head)
{
	 int num = 0;
	 int flag = 0;
	 ListNode *p = NULL;
	 cin >> num;
	 
	 Head = (ListNode *)malloc(sizeof(ListNode));
	 while(num != 0)
	 {
		  if(flag == 0)
		  {  
			   Head->data = num;
			   Head->next = NULL;
			   flag = 1;
			   p = Head;
		  }
		  else
		  {
			   ListNode *cur = (ListNode *)malloc(sizeof(ListNode));
			   cur->data = num;
			   cur->next = NULL;
			  
			   p->next = cur;
			   p = cur;
		  } 
		  cin >> num;
	 }
	// return temp;
}

// 
void printList(ListNode *Head)
{
	 if(Head == NULL)
	 {
		  cout << "Head empty"<<endl;
		  return ;
	 }
	 ListNode *p = Head;
	 while(p != NULL)
	 {
		  cout << p->data <<" ";
		  p = p->next;
	 }
}
// k ， n-k-1 
ListNode *FindK1(ListNode *Head,unsigned int k)
{
	 if(Head == NULL)
	 {
		  return NULL;
	 }
	 ListNode *pCur = Head;
	 // nNum， 
	 unsigned int nNum = 0;
	 // 
	 while(pCur->next != NULL)
	 {
		  pCur = pCur->next;
		  nNum++;
	 }
	 //
	 if(nNum < k)
	 {
		  return NULL;
	 }
	 pCur = Head;
	 for(unsigned int i=0; i < nNum-k; i++)
	 {
		  pCur = pCur->next;
	 }
	 return pCur;
}
// ， ， k 。
ListNode *FindK2(ListNode *Head,unsigned int k)
{
	 if(Head == NULL)
	 {
		  return NULL;
	 }
	 ListNode *pHead = Head;
	 ListNode *pBehind = NULL;
	 for(unsigned int i=0; i<k; ++i)
	 {
		  if(pHead->next != NULL)
		  {
			   pHead = pHead->next;
		  }
		  else
		  {
			   return NULL;
		  }
	 }
	 pBehind = Head;
	 while(pHead->next != NULL)
	 {
		  pHead = pHead->next;
		  pBehind = pBehind->next;
	 }
	 return pBehind;
}
// 
void main()
{
	 ListNode *List = NULL;
	 cout << " ：";
	 createList(List);
	 cout << " ：";
	 printList(List);
	 ListNode *p = FindK1(List,4);
	 cout << endl <<" ：" <<p->data <<endl;
	 ListNode *q = FindK2(List,5);
	 cout << " ：" <<q->data <<endl;
}

 
実行結果:
チェーンテーブルを作成する:1 2 3 4 5 6 7 8 9 0チェーンテーブル要素:1 2 3 4 5 6 8 9最後から4番目:5最後から5番目:4任意のキーを押して続行してください.