C++의 정렬된 연결 목록에서 중앙값 찾기

이 문제에서는 N개의 요소로 구성된 정렬된 연결 목록이 제공됩니다. 우리의 임무는 정렬된 연결 목록에서 중앙값을 찾는 것입니다. .

정렬된 연결 목록 모든 요소가 특정 순서로 정렬된 간단한 연결 목록입니다. 예 − 4 -> 6 -> 7 -> 9 -> NULL

중앙값 연결 목록의 중간 요소입니다. N이 홀수인 것처럼 찾을 수 있습니다. 중앙값은 (n/2) ^th 입니다. 요소

N이 짝수인 경우 중앙값은 (n/2) ^번째 의 평균입니다. 요소 및 (n/2 + 1) ^번째 요소.

문제를 이해하기 위해 예를 들어 보겠습니다.

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

솔루션 접근 방식

문제에 대한 간단한 해결책은 연결 목록을 탐색하여 연결 목록의 모든 요소를 ​​계산하는 것입니다.

이제 개수가 홀수이면 연결 목록의 N/2번째 요소까지 연결 목록을 다시 탐색합니다.

개수가 짝수이면 N/2번째 요소와 N/2 + 1번째 요소까지 순회하여 더하고 2로 나눕니다.

대체 접근 방식

문제를 해결하는 또 다른 방법은 두 포인터 탐색을 사용하여 연결 목록을 탐색하고 연결 목록의 요소 수를 찾는 것입니다.

다음은 요소 수를 세지 않고 중앙값을 찾는 알고리즘입니다. 그것들은 조건에 따라 두 개의 포인터 pointer1과 pointer2입니다.

포인터1이 NULL이 아니면 포인터2가 중앙값입니다.

pointer1이 NULL이면 (pointer2의 노드 + pointer2 -> 데이터의 이전)/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