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個變數。 1為最小，other為次小，然後遍歷鍊錶，每次遇到更小的元素時，將最小的變數更新到次小，新的較小的就變成最小的。因此，每當一個元素小於最小的元素時，第二小的元素就會變成最小的，最小的元素就會變成新元素。如果不是，我們比較第二小的元素並確定當前元素是否小於第二小的元素，然後進行相應的更新。

#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)。如果您覺得上述資訊有用，那麼請務必造訪我們的官方網站以了解更多有關程式設計的相關主題。

以上是C++程式：在鍊錶中找到第二小的元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！