天天看點
傳回

單連結清單 （面試題）

關于單連結清單的基本操作，之前已經總結過了，那些掌握之後算是了解了單連結清單是什麼？不過現在面試的題中，肯定不會隻讓你回答單連結清單的基礎操作，總是會改變一些東西，或是擴充一下。

下面就是一些關于單連結清單的擴充内容：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#pragma warning (disable:4996)
#define DataType int
typedef struct PNode{
 DataType data;
 struct PNode* next;
}Node,*PNode;
//建立新的節點
PNode BuyNode(DataType data);
//初始化單連結清單
void InitList(PNode* pHead);
//尾插
void PushList(PNode* pHead, DataType data);
//列印單連結清單
void PrintList(PNode pHead);
// 從尾到頭列印單連結清單
void PrintListFromTail2Head(PNode pHead);
// 删除無頭單連結清單的非尾結點
void DeleteNotTailNode(PNode pos);
// 在無頭單連結清單非頭結點前插入置為data的結點
void InsertNotHeadNode(PNode pos, DataType data);
// 用單連結清單實作約瑟夫環
PNode JosephCircle(PNode pHead, size_t M);
// 逆置單連結清單--三個指針
PNode ReverseList(PNode pHead);
// 逆置單連結清單--頭插法
PNode ReverseList_P(PNode pHead);
// 對單連結清單進行冒泡排序--升序
void BubbleSort(PNode pHead);
// 查找單連結清單的中間結點，要求隻能夠周遊一次連結清單
PNode FindMidNode(PNode pHead);
// 查找單連結清單的倒數第K個結點，隻能夠周遊一次連結清單
PNode FindLastKNode(PNode pHead, size_t K);
//// 删除單連結清單的倒數第K個結點
//PNode DeleteLastKNode(PNode pHead, size_t K);
//
//// 合并兩個已序單連結清單，合并之後依然有序
//PNode MergeList(PNode pHead1, PNode pHead2);

有些内容就不能按照正常的思路來看，我記得第一次上課的時候，老師出了一道智力題，

說是有兩隻分布不均勻的香，但是它們都能燃燒一個小時，如果我們想要測量一刻鐘的時間，該如何做？

當時很多人都說将香掐成兩段，然而，香并不是均勻的，是以不行。

最後給出了答案：将兩隻香同時點燃，不過，要一隻點燃一頭，另一隻點燃兩頭，這樣，等其中一隻燃燒完了之後，時間剛好過了半個小時，再将另一頭也點上，這樣，剩餘的香就能燃燒一刻鐘的時間了。

同樣的道理，這裡的一些問題也是這樣的想法，比如求中點的問題，隻要給出兩個指針，慢的一次走一步，快的一次走兩步，等快的走到最後，那麼慢的剛好走到中間。

下面就是這些函數的實作了：

#include"LinkList.h"
//建立新的節點
PNode BuyNode(DataType data)
{
 PNode Node = (PNode)malloc(sizeof(Node));
 if (Node)
 {
  Node->data = data;
  Node->next = NULL;
 }
 return Node;
}
//初始化單連結清單
void InitList(PNode * pHead)
{
 assert(pHead);
 (*pHead) = NULL;
}
//尾插
void PushList(PNode* pHead, DataType data)
{
 assert(pHead);
 PNode NewNode = BuyNode(data);
 if (NULL==(*pHead))
 {
  (*pHead) = NewNode;
 }
 else
 {
  PNode pCur = (*pHead);
  while (pCur->next)
  {
   pCur = pCur->next;
  }
  pCur->next = NewNode;
 }
}
void PrintList(PNode pHead)
{
 PNode pCur = pHead;
 while (pCur)
 {
  printf("%d ", pCur->data);
  pCur = pCur->next;
 }
 printf("\n");
}
// 從尾到頭列印單連結清單
void PrintListFromTail2Head(PNode pHead)
{
 if (pHead)
 {
  PrintListFromTail2Head(pHead->next);//運用遞歸的思想，找出最後一個節點，列印
  printf("%d ", pHead->data);
 }
 printf("\n");
}
// 删除無頭單連結清單的非尾結點，不能周遊單連結清單
void DeleteNotTailNode(PNode pos)
{
 if (NULL == pos)//如果pos的位置為空，直接傳回
 {
  return;
 }
 PNode pDel = pos->next;//将pos後面的節點儲存
 pos->data = pDel->data;//将pos後面的值，賦給pos中的data
 pos->next = pDel->next;//将pos的下一個位置指向待删除的下一個位置
 free(pDel);//釋放空間
}
// 在無頭單連結清單非頭結點前插入置為data的結點
void InsertNotHeadNode(PNode pos, DataType data)
{
 if (NULL == pos)
 {
  return;
 }
 PNode NewNode = BuyNode(pos->data);
 if (NewNode)
 {
  NewNode->next = pos->next;
  pos->next = NewNode;
  pos->data = data;
 }
}
// 用單連結清單實作約瑟夫環
PNode JosephCircle(PNode pHead, size_t M)
{
 if (NULL == pHead)
 {
  return;
 }
 PNode pCur = pHead;
 while (pCur != pCur->next)
 {
  size_t k = M;
  while (--k)
  {
   pCur = pCur->next;
  }
  PNode pDel = pCur->next;
  pCur->data = pDel->data;
  pCur->next = pDel->next;
  free(pDel);
 }
 return pCur;
}
// 逆置單連結清單--三個指針
PNode ReverseList(PNode pHead)//不太了解
{
 if (NULL == pHead || NULL == pHead->next)
 {
  return pHead;
 }
 PNode prev = pHead;
 PNode pCur = prev->next;
 PNode pnext = pCur->next;
 while (pnext)
 {
  pCur->next = prev;
  prev = pCur;
  pCur = pnext;
  pnext = pnext->next;
 }
 pCur->next = prev;
 pHead->next = NULL;
 return pCur;
}
// 逆置單連結清單--頭插法
PNode ReverseList_P(PNode pHead)
{
 if (NULL == pHead || NULL == pHead->next)
 {
  return NULL;
 }
 PNode pCur = pHead->next;
 PNode NewNode = NULL;
 while (pCur)
 {
  pHead->next = NewNode;
  NewNode = pHead;
  pHead = pCur;
  pCur = pCur->next;
 }
 pHead->next = NewNode;
 NewNode = pHead;
 return NewNode;
}
// 對單連結清單進行冒泡排序--升序
void BubbleSort(PNode pHead)
{
 if (NULL == pHead || NULL == pHead->next)
 {
  return;
 }
 PNode pCur = pHead;
 PNode pTail = NULL;
 DataType flag = ;
 while (pTail != pHead)
 {
  pCur = pHead;
  while (pCur->next != pTail)
  {
   //結構體中的next定義成PNode*的形式，才能使next繼續間接通路，
   if ((pCur->data) > (pCur->next->data)) 
   {
    DataType temp = pCur->data;         //交換
    pCur->data = pCur->next->data;
    pCur->next->data = temp;
    flag = ;
   }
   pCur = pCur->next;
  }
  if (!flag)
  {
   return;
  }
  pTail = pCur;
 }
}
// 查找單連結清單的中間結點，要求隻能夠周遊一次連結清單
PNode FindMidNode(PNode pHead)
{
 if (NULL == pHead || NULL == pHead->next)
 {
  return;
 }
 //使用一快一慢兩個指針，快的是慢的的二倍
 PNode pslow = pHead;
 PNode pfast = pHead;
 while (pfast&&pfast->next)//分兩種情況考慮
 {
  pslow = pslow->next;
  pfast = pfast->next->next;
 }
 return pslow;//快的指針到尾部，慢的指針就在中間，是以傳回慢的指針即可
}
// 查找單連結清單的倒數第K個結點，隻能夠周遊一次連結清單
PNode FindLastKNode(PNode pHead, size_t K)
{
 if (NULL == pHead || K == )
 {
  return NULL;
 }
 PNode pslow = pHead;
 PNode pfast = pHead;
 while (--K)//先讓快的指針走K步
 {
  if (NULL == pfast)//如果K的值大于節點數，傳回空
  {
   return NULL;
  }
  pfast = pfast->next;
 }
 while (pfast->next)//再一起走，等到快的走到尾部，慢的剛好到倒數第K個節點
 {
  pfast = pfast->next;
  pslow = pslow->next;
 }
 return pslow;//傳回慢的指針即可
}
 //删除單連結清單的倒數第K個結點
PNode DeleteLastKNode(PNode pHead, size_t K)
{
 if (NULL == pHead || NULL == pHead->next)
 {
  return NULL;
 }
 PNode pos = FindLastKNode(pHead, K);
 Earse(pHead, pos);
}
 //合并兩個已序單連結清單，合并之後依然有序
PNode MergeList(PNode pHead1, PNode pHead2)
{
 if (NULL == pHead1)
 {
  return pHead2;
 }
 if (NULL == pHead2)
 {
  return pHead1;
 }
 PNode pTail= NULL;
 PNode NewNode = NULL;
 if (pHead1->data < pHead2->data)
 {
  pTail = pHead1;
  pHead1 = pHead1->next;
 }
 else
 {
  pTail = pHead2;
  pHead2 = pHead2->next;
 }
 NewNode = pTail;
 while (pHead1&&pHead2)
 {
  if (pHead1->data < pHead2->data)
  {
   pTail->next = pHead1;
   pTail = pHead1;
   pHead1 = pHead1->next;
  }
  else
  {
   pTail->next = pHead2;
   pTail = pHead2;
   pHead2 = pHead2->next;
  }
 }
 if (pHead1)
 {
  pTail->next = pHead1;
 }
 else
 {
  pTail->next = pHead2;
 }
 return NewNode;
}
           
#include"LinkList.h"
void FunTest()
{
 PNode pHead;
 InitList(&pHead);
 PushList(&pHead,);
 PushList(&pHead, );
 PushList(&pHead, );
 PushList(&pHead, );
 PushList(&pHead, );
 PrintList(pHead);
 PrintListFromTail2Head(pHead);
 //
 //JosephCircle(pHead, 3);
 //PrintListFromTail2Head(pHead);
 PNode p=FindMidNode(pHead);
 printf("%d\n", p->data);
 PNode p1 = FindLastKNode(pHead, );
 printf("%d\n", p1->data);
 BubbleSort(pHead);
 PrintList(pHead);
}
int main()
{
 FunTest();
 system("pause");
 return ;
}

程式寫的很欠缺，有的地方還需再進行，如果，你們有什麼意見或建議，請評論……

資料結構 單連結清單 面試題 中間節點 逆置單連結清單 排序單連結清單
上一篇: 關于紋理和紋理坐标的解釋。網址是個不錯的D3D學習網址
下一篇: 單連結清單的相關面試題（二）

繼續閱讀