C++程式：查詢連結串列中第二小的元素

資料元素的有序集合，每個元素都連結到其下一個元素（有時還有其前驅元素）。假設存在一個連結串列，我們需要找到第二小的元素。以下是幾種情況。

讓我們假設一些簡單的輸入和輸出場景

讓我們假設這種情況：我們有一個連結串列，其中包含元素“8->4->6->2->9”。遍歷整個連結串列後，第二小的元素將是8。

Input = 8->4->6->2->9
Output = 8

連結串列的程式設計實現方式

Node* head = new Node(8);
head->next = new Node(4);
head->next->next = new Node(6);
head->next->next->next = new Node(2);
head->next->next->next->next = new Node(9);
result = solve(head);

考慮另一種情況，連結串列中的每個元素都具有相同的值。遍歷所有元素後，將找不到連結串列中的第二小元素。因為連結串列中的每個元素都具有相同的值。

Input = 1->1->1->1->1->1
Output = There is no second smallest element in Linked list

演算法

執行此任務需要遵循以下步驟

  • 分配兩個變數 (S1, S2)

  • S1 將儲存連結串列中最小的元素

  • S2 將儲存連結串列中第二小的元素。

  • 每次迭代，最小的元素將移動到 S1，並在遇到新的最小值時移動到 S2

  • 當最小值 (S1) 小於新最小值時，新的最小值將成為最小值 (S1)。

  • 新的最小值將成為最小值 (S1)，而原來的最小值 (S1) 將移動到第二小值 (S2)。

  • 經過所有可能的遍歷後，最終輸出中將得到第二小的元素作為結果。

示例

在 C++ 實現中，我們可以保留 2 個變數。一個用於最小值，另一個用於第二小值，然後遍歷連結串列並更新這些變數，每次遇到較小的元素時，最小值移動到第二小值，新的最小值成為最小值。因此，每當一個元素小於最小值時，第二小值成為最小值，而最小值成為新元素。如果不是，我們將比較第二小值，並確定當前元素是否小於第二小值，然後相應地進行更新。

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node *next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
int solve(Node* root) {
   int s1=root->val, s2=root->val;
   while(root) {
      if(root->val <= s1) {
         s2 = s1;
         s1 = root->val;
      } else if(root->val < s2) {
         s2 = root->val;
      }
      root = root->next;
   }
   return s2;
}
int main() {
   Node* head = new Node(5);
   head->next = new Node(8);
   head->next->next = new Node(9);
   head->next->next->next = new Node(2);
   head->next->next->next->next = new Node(4);
   cout << "Second smallest element in the linked list is : " << solve(head);
   return 0;
}

輸出

Second smallest element in the linked list is: 4

結論

時間複雜度為 O(n)，因為我們只遍歷連結串列一次。如果您發現上述資訊有用，請務必訪問我們的官方網站，瞭解更多關於程式設計相關主題的資訊。

更新於：2022年8月10日

瀏覽量：280

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告