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

启动您的职业生涯

完成课程获得认证

开始学习
广告