C++のソートされたリンクリストで中央値を見つける

この問題では、N個の要素で構成されるソートされたリンクリストが与えられます。私たちのタスクは、並べ替えられたリンクリストの中央値を見つけることです。 。

ソートされたリンクリスト は、すべての要素が特定の順序でソートされている単純なリンクリストです。 例 − 4-> 6-> 7-> 9-> NULL

中央値 リンクリストの中央の要素です。 Nが奇数であるかのように見つけることができます：中央値は（n / 2） ^th 要素

Nが偶数の場合-s中央値は（n / 2） ^th の平均です 要素と（n / 2 + 1） ^th 要素。

問題を理解するために例を見てみましょう

Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL
Output: 4

ソリューションアプローチ

この問題の簡単な解決策は、リンクリストのすべての要素をトラバースしてカウントすることです。

ここで、カウントが奇数の場合、リンクリストのN/2番目の要素までリンクリストを再度トラバースします。

カウントが偶数の場合、N/2番目の要素とN/2 + 1番目の要素までトラバースし、それらを加算して2で除算します。

代替アプローチ

この問題を解決する別のアプローチは、2つのポインタートラバーサルを使用してリンクリストをトラバースし、リンクリストの要素の数を見つけることです。

これは、要素の数を数えずに中央値を見つけるためのアルゴリズムです。それらは、条件に基づいて、pointer1とpointer2の2つのポインターです。

ポインター1がNULLでない場合、ポインター2は中央値です。

ポインター1がNULLの場合、（ポインター2のノードの前+ポインター2->データ）/2。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void findMedianValue(Node* head){
   Node* ptr1 = head;
   Node* ptr2 = head;
   Node* prev = head;
   if (head != NULL) {
      while (ptr2 != NULL && ptr2->next != NULL) {
         ptr2 = ptr2->next->next;
         prev = ptr1;
         ptr1 = ptr1->next;
      }
      if (ptr2 != NULL)
         cout<<ptr1->data;
      else
         cout<<float(ptr1->data + prev->data) / 2;
   }
}
void pushVal(struct Node** head_ref, int new_data){
   Node* new_node = new Node;
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
int main(){
   struct Node* head = NULL;
   pushVal(&head, 3);
   pushVal(&head, 5);
   pushVal(&head, 6);
   pushVal(&head, 8);
   pushVal(&head, 9);
   pushVal(&head, 11);
   cout<<"The median of the linked list is ";
   findMedianValue(head);
   return 0;
}

出力

The median of the linked list is 7