C++ program: Find the second smallest element in a linked list

An ordered collection of data elements. Each data element has a link to its next element (sometimes its previous element). Assuming there is a linked list, then We need to find the second smallest element. Below is the following scenario.

Let’s assume some simple input and output scenarios

Assume this scenario, we have a linked list, the elements contained in it are "8->4->6->2->9,". Then after iterating the entire linked list, the second smallest element is 8.

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

Programming implementation of linked list

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);

Consider another situation where every element in the linked list has the same value. After iterating through all elements, the second smallest element will not be found in the linked list. Since each element in the linked list contains the same value.

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

algorithm

Here are the steps to follow when performing the task

• Assign two variables (S1, S2)

• S1 will save the smallest element in the linked list

• S2 will hold the second smallest element in the linked list.

• Each iteration, the smallest element will be moved to S1, and when it is encountered, it will be moved to S2

• When the minimum (S1) is smaller than the new smaller value, the new smaller will become the minimum (S1).

• The new smaller one will become smaller (S1) and the smaller one (S1) will move to the second smaller one (S2).

• After each possible traversal, the second smallest element in the final output will be the output.

Example

In the C implementation, we can keep 2 variables. 1 is the smallest, other is the second smallest, and then the linked list is traversed. Every time a smaller element is encountered, the smallest variable is updated to the next smallest, and the new smaller one becomes the smallest. So whenever an element is smaller than the smallest element, the second smallest element becomes the smallest and the smallest element becomes the new element. If not, we compare the second smallest element and determine if the current element is smaller than the second smallest element, and update accordingly.

#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;
}

Output

Second smallest element in the linked list is: 4

in conclusion

Traverse the linked list once, the time complexity is O(n). If you found the above information useful, then do visit our official website to know more related topics about programming.

The above is the detailed content of C++ program: Find the second smallest element in a linked list. For more information, please follow other related articles on the PHP Chinese website!