單連結清單常見操作

題注：

《程式員面試寶典》有相關習題，但思路相對不清晰，排版有錯誤，本文對此參考相關書籍和自己觀點進行了重寫，供大家參考。

1.查找連結清單元素

Step1：置查找标記bfound=false;判斷連結清單是否為空，是，提示“不能查找空連結清單”；否，進入step2。

Step2：從連結清單頭開始查找，判斷（目前點的info是否與待查找元素值相等&&指針未指向末尾），是，“查找結束，bfound=true”，否，繼續查找。

Step3：判斷bfound= = true，是，“提示查找成功”，否，“提示查找失敗”。

/查找單連結清單元素
template<typename Type>
void linkedlistType<Type>::search(const Type& searchItem)
{
       nodeType<Type> *current;
       bool found = false;
 
       if(first == NULL)                                          //1.空連結清單
       {
              cout << "WARNING: Can not search an empty list!" << endl;
              return;
       }
       else
       {
              current = first;
              while(!found && current != NULL)
              {
                     if(current->info == searchItem)
                     {
                            found = true;
                            break;
                     }
                     else
                     {
                            current = current->link;
                     }
              }
              if(found)
              {
                     cout << searchItem << " was found in the List! " << endl;
              }
              else
              {
                     cout << searchItem << " was not found in the List! " << endl;
              }
       }
}

2.删除連結清單元素值

Step1：置查找标記bfound=false; 判斷連結清單是否為空，是，提示“不能對空連結清單進行删除操作”；否，進入step2。

Step2：判斷待删除元素值是否與頭節點元素值相等，是，調整頭節點指針；否，進入step3。

Step3：判斷連結清單中是否存在該元素，否，“提示元素不存在”；是，進入step4。

Step4：判定要删除元素是否與末尾節點元素值相等，是，調整末尾last指針；否，此時為中間節點，需要調整trailCurrent和Current指針的指向。

//删除單連結清單元素
template<typename Type>
void linkedlistType<Type>::deleteNode(const Type& deleteItem)
{
       nodeType<Type> *tempNode = new nodeType<Type>;
       nodeType<Type> *current = new nodeType<Type>;
       nodeType<Type> *trailCurrent = new nodeType<Type>;
       bool found;
      
       //連結清單為空 case1
       if(first == NULL)
       {
              cout << "Can not delete an empty List!" << endl;
       }
       else
       {
              if( first->info == deleteItem )
              {
                     //要删除的也是第一個節點(僅一個節點，或不止一個節點) case2
                     tempNode = first;
                     first = first->link;
                     if(first == NULL)
                     {
                            last = NULL;
                     }                         
                     delete tempNode;
              }
              else
              {
                     //先查找，後判斷... case3
                     found = false;
                     trailCurrent = first;
                     current = first->link;
 
                     while((!found) && (current != NULL))
                     {
                            if(deleteItem  != current->info)
                            {
                                   trailCurrent = current;
                                   current = current->link;
                            }
                            else
                            {
                                   found = true;
                            }
                     }
 
                     if(found)
                     {
                            //能找到...
                            trailCurrent ->link = current->link;
 
                            if(current == last)
                            {
                                   last = trailCurrent; //case 3a
                            }
                            delete current;         //case 3b
                     }
                     //不存在該點...case4
                     else
                     {
                            cout << "The deleteItem is not Exist in the List! " << endl;
                     } //end else
              }//end else
       }//end else
      
}// end deleteNode

3.單連結清單逆置[疊代實作]

Step1：判斷連結清單是否為空，是，提示“不能對空連結清單進行逆置操作“；否，進入Step2；

Step2：從第2個節點開始，依次将每個節點插入到第一個節點的前面，判斷指針是否指向了連結清單尾部，是，傳回頭指針結束；否，繼續疊代後面的連結清單元素。

template<typename Type>
nodeType<Type>* linkedlistType<Type>::reverseList()   //逆置單連結清單
{
       if(first == NULL)
       {
              cout << "Can't reverse empty List!" << endl;
       }
       else
       {
              nodeType<Type>* p = first;
              nodeType<Type>* q = p->link;
 
              while(q != NULL)
              {
                     p->link = q->link;
                     q->link = first;
                     first = q;
                     q = p->link;
              }
       }
       return first;
}

4．單連結清單排序[直接插入排序]

思路：分為以下幾種情況：

1）單連結清單為空；

2）單連結清單非空，但僅含一個元素，無需排序已經有序；

3）待插入元素小于頭結點的元素；

4）待插入元素為前已有序的中間的元素值；

5）待插入的元素前所有元素都比其小，直接插到末尾。

分别用lastInOrder記錄已經有序的最後一個節點，firstOutOfOrder第一個尚未排序（正待參與）排序的節點。current用于記錄循環的節點，trailCurrent記錄current前的節點。

template<typename Type>
void linkedlistType<Type>::sortList()     //單連結清單排序
{
       nodeType<Type>* current;
       nodeType<Type>* trailCurrent;
       nodeType<Type>* lastInOrder;
       nodeType<Type>* firstOutOfOrder;
 
       lastInOrder = first;
 
       //case1,表為空.
       if(first == NULL)
       {
              cout << "Can't Sort of empty List!" << endl;
              return;
       }
 
       //case2,表不為空,但表長為1,僅含1個元素.
       if(first->link == NULL)
       {
              cout << "The List Was Already ordered!" << endl;
              return;
       }
 
       while(lastInOrder->link != NULL)
       {
              firstOutOfOrder = lastInOrder->link;    
              //case3,要插入的元素小于第1個元素.
              if(firstOutOfOrder->info < first->info)
              {
                     lastInOrder->link = firstOutOfOrder->link;
                     firstOutOfOrder->link = first;
                     first = firstOutOfOrder;
              }
              else
              {    
                     trailCurrent = first;
                     current = first->link;
                     while(current->info < firstOutOfOrder->info)
                     {
                            trailCurrent = current;
                            current = current->link;
                     }
 
                     //case4,要插入的元素在前已有序元素的中間.
                     if(trailCurrent != lastInOrder)
                     {
                            lastInOrder->link = firstOutOfOrder->link;
                            firstOutOfOrder->link = current;
                            trailCurrent->link = firstOutOfOrder;
                     }
                     else
                     {
                            //case5,要插入的元素大于最後一個已經有序的元素.
                            lastInOrder = lastInOrder->link;
                     }//end else
              }//end else
       }//end while
}

5.單連結清單在不知道連結清單長度的前提下求連結清單中間節點的值。

思路：分以下幾種情況：

1）連結清單為空；

2）連結清單非空，但僅有一個或兩個節點；可以直接傳回第一個節點的元素值。

3）連結清單非空，但含有三個或三個以上的節點，可以通過定義兩個指針，一個指針的跳步為2次的時候，另一個指針的跳步為1次，當跳至結尾時，另一個節點恰好在中間位置。

//不知道表長的前提下求單連結清單中間元素

template<typename Type>
Type linkedlistType<Type>::midValOfList()         
{
       nodeType<Type> *current;
       nodeType<Type> *halfCurrent;
 
       if(first == NULL)                                //case1,沒有節點
       {
              cout << "連結清單為空!" << endl;
              return -1;
       }
       else if(first->link == NULL || first->link->link == NULL) //case2,僅一個節點或兩個節點.
       {
              return first->info;
       }
       else                                   //case3,含有三個或三個以上的節點.
       {
              current = first;
              halfCurrent = current;
 
              while(current->link != NULL)
              {
                     current = current->link;
                     if(current->link != NULL)
                     {
                            if(current->link != NULL)
                            {
                                   halfCurrent = halfCurrent->link;
                                   current = current->link;
                            }//end if
                     }
              }//end while
              return halfCurrent->info;
       }//end else
}

6.單連結清單建立

思路：單連結清單的建立可分為根據插入新節點的位置的不同而分為兩種，1：在連結清單末尾插入元素的建立方式；2：在連結清單前面插入元素建立連結清單的方式。

對應1末尾插入分為兩步：

Step1：如果目前連結清單為空，則置first=last=newNode；否則，進入Step2。

Step2：插入新結點元素，修改last指針。

對于2連結清單first指針前插入：主要需要保證插入元素後，修正first節點即可。

//正向末尾插入
template<typename Type>
nodeType<Type>* linkedlistType<Type>::buildListForward()
{
       nodeType<Type>  *newNode;
 
       int num;
       cout << " Enter a list of integer end with -999. " << endl;
       cin >> num;
       while(num != -999)
       {
              //..add
              newNode = new nodeType<Type>;
              newNode->info = num;
              newNode->link = NULL;
 
              if(first==NULL)
              {
                     first = newNode;
                     last = newNode;
              }
              else
              {
                     last->link = newNode;
                     last = newNode;
              }
              cin >> num;
       }
       return first;
}
 
//反向表頭插入，從前面插入...
template<typename Type>
nodeType<Type>* linkedlistType<Type>::buildListBackward()
{
       nodeType<Type>  *newNode;
 
       int num;
       cout << " Enter a list of integer end with -999. " << endl;
       cin >> num;
       while(num != -999)
       {
              //..add
              newNode = new nodeType<Type>;
              newNode->info = num;
              newNode->link = first;
              first = newNode;
              cin >> num;
       }
       return first;
}

7.單連結清單的測量長度

思路：連結清單的長度等效為節點個數，指針非空則循環判斷即可。

//求解連結清單長度
template<typename Type>
int linkedlistType<Type>::length()
{
       int count = 0;
       nodeType<Type> *current;
       current = first;
 
       while(current != NULL)
       {
              count++;
              current = current->link;
       }
       return count; //節點個數等效為長度.
}

8.單連結清單的插入

思路：連結清單的插入也同連結清單的建立一樣分為前向、後向插入兩種形式，注意first、last指針的指向問題。

//在前面插入
template<typename Type>
void linkedlistType<Type>::insertFirst(const Type& newItem)
{
       //last no use.
       nodeType<Type> *newNode = new nodeType<Type>;
       newNode->info = newItem;
       newNode->link = first;   //在前面加入...
       first = newNode;
}
 
//在後面插入元素...
template<typename Type>
void linkedlistType<Type>::insertLast(const Type& newItem)
{
       nodeType<Type> *newNode = new nodeType<Type>;
       newNode->info = newItem;
       newNode->link = NULL;   //在後面加入...
 
       if(first == NULL)
       {
              first = newNode;
              last = newNode;
       }
       else
       {
              last->link = newNode;
              last = newNode;
       }
}

後續陸續會有棧、隊列、二叉樹、圖、排序、查找等的相關分析，希望大家關注！

作者：銘毅天下

來源：CSDN

原文：

https://blog.csdn.net/laoyang360/article/details/7858469

資料結構面試之一——單連結清單常見操作單連結清單常見操作

單連結清單常見操作

題注：

1.查找連結清單元素

2.删除連結清單元素值

3.單連結清單逆置[疊代實作]

4．單連結清單排序[直接插入排序]

5.單連結清單在不知道連結清單長度的前提下求連結清單中間節點的值。

6.單連結清單建立

7.單連結清單的測量長度

8.單連結清單的插入

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希