Замените каждый узел его счетчиком Surpasser в связанном списке

Опубликовано: 5 Января, 2022

Учитывая LinkedList, замените значение каждого узла его количеством превышающих. Это количество элементов, которые больше справа от него.

Примеры:

Input : 10->12->5->40->21->70->1->49->37->NULL
Output : 6->5->5->2->3->0->2->0->0->NULL
Explanation :
Element in the first node is 10 and the number of elements to the right of the node that are greater than 10 is 6. Therefore replace the node with 6.
Element in the first node is 12 and the number of elements to the right of the node that are greater than 12 is 5. Therefore replace the node with 5.
Similarly, replace for all the elements in the list.

Input : 5->4->6->3->2->NULL
Output : 1->1->0->0->0->NULL

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простой подход

  1. Возьмем два указателя p и x . Указатель p используется для обхода списка, а x используется для обхода правой половины списка для каждого узла.
  2. Инициализируйте счетчик переменных для подсчета узлов больше, чем текущие узлы.
  3. Пройдите по всем узлам в списке, используя указатель p.
    • Установите счетчик на 0.
    • Инициализируйте указатель x, чтобы он указывал на текущий узел p .
    • Подсчитайте количество узлов, которые больше текущего узла.
    • Замените текущий узел на счетчик.
  4. Повторяйте шаг 4, пока список не будет пройден полностью.

Ниже представлена реализация описанного выше подхода:

C ++

// C++ program to replace the nodes
// with their surpasser count
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node {
data; int
struct Node* next;
};
// Utility function to create a new Node
Node* newNode( data) int
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to display the linked list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " " ;
node = node->next;
}
}
// Function to check Surpasser Count
void replaceNodes(Node* head)
{
// Pointer used to traverse through
// all the nodes in the list
Node* p = head;
// Pointer used to traverse through the right
// elements to count the greater elements
Node* x = NULL;
// Variable to count the number of
// elements greater than the
// current element on right
int count = 0;
int i;
// Traverse through all the elements
// in the list
while (p != NULL) {
count = 0;
i = 0;
// Initialize x to current node
x = p;
// Check or count the number of nodes
// that are greater than the current
// node on right
while (x != NULL) {
if (x->data > p->data)
count++;
x = x->next;
}
// Replace the node data with the
// count of elements greater than
// the current element
p->data = count;
p = p->next;
}
}
// Driver code
int main()
{
// Creating the linked list
Node* head = newNode(10);
head->next = newNode(12);
head->next->next = newNode(5);
head->next->next->next = newNode(40);
head->next->next->next->next = newNode(21);
head->next->next->next->next->next = newNode(70);
head->next->next->next->next->next->next = newNode(1);
head->next->next->next->next->next->next->next = newNode(49);
head->next->next->next->next->next->next->next->next = newNode(37);
replaceNodes(head);
printList(head);
return 0;
}

Джава

// Java program to replace the nodes
// with their surpasser count
class GFG {
// A linked list node
static class Node {
data; int
Node next;
};
// Utility function to create a new Node
static Node newNode( data) int
{
Node temp = new Node();
temp.data = data;
temp.next = null ;
return temp;
}
// Function to display the linked list
static void printList(Node node)
{
while (node != null ) {
System.out.print(node.data+ " " );
node = node.next;
}
}
// Function to check Surpasser Count
static void replaceNodes(Node head)
{
// Pointer used to traverse through
// all the nodes in the list
Node p = head;
// Pointer used to traverse through the right
// elements to count the greater elements
Node x = null ;
// Variable to count the number of
// elements greater than the
// current element on right
int count = 0 ;
int i;
// Traverse through all the elements
// in the list
while (p != null ) {
count = 0 ;
i = 0 ;
// Initialize x to current node
x = p;
// Check or count the number of nodes
// that are greater than the current
// node on right
while (x != null ) {
if (x.data > p.data)
count++;
x = x.next;
}
// Replace the node data with the
// count of elements greater than
// the current element
p.data = count;
p = p.next;
}
}
// Driver code
public static void main(String[] args) {
// Creating the linked list
Node head = newNode( 10 );
head.next = newNode( 12 );
head.next.next = newNode( 5 );
head.next.next.next = newNode( 40 );
head.next.next.next.next = newNode( 21 );
head.next.next.next.next.next = newNode( 70 );
head.next.next.next.next.next.next = newNode( 1 );
head.next.next.next.next.next.next.next = newNode( 49 );
head.next.next.next.next.next.next.next.next = newNode( 37 );
replaceNodes(head);
printList(head);
}
}
// This code has been contributed by 29AjayKumar

Python3

# Python3 program to replace the nodes
# with their surpasser count
# A linked list node
class Node:
def __init__( self , data):
self .data = data
self . next = None
# Function to display the linked list
def printList(node):
while node ! = None :
print (node.data, end = " " )
node = node. next
# Function to check Surpasser Count
def replaceNodes(head):
# Pointer used to traverse through
# all the nodes in the list
p = head
# Pointer used to traverse through
# the right elements to count the
# greater elements
x = None
# Variable to count the number of
# elements greater than the
# current element on right
count = 0
# Traverse through all the elements
# in the list
while p ! = None :
count = 0
# Initialize x to current node
x = p
# Check or count the number of nodes
# that are greater than the current
# node on right
while x ! = None :
if x.data > p.data:
count + = 1
x = x. next
# Replace the node data with the
# count of elements greater than
# the current element
p.data = count
p = p. next
# Driver code
if __name__ = = "__main__" :
# Creating the linked list
head = Node( 10 )
head. next = Node( 12 )
head. next . next = Node( 5 )
head. next . next . next = Node( 40 )
head. next . next . next . next = Node( 21 )
head. next . next . next . next . next = Node( 70 )
head. next . next . next . next . next . next = Node( 1 )
head. next . next . next . next . next . next . next = Node( 49 )
head. next . next . next . next . next . next . next . next = Node( 37 )
replaceNodes(head)
printList(head)
# This code is contributed by Rituraj Jain

C #

// C# program to replace the nodes
// with their surpasser count
using System;
class GFG
{
// A linked list node
public class Node
{
public data; int
public Node next;
};
// Utility function to create a new Node
static Node newNode( data) int
{
Node temp = new Node();
temp.data = data;
temp.next = null ;
return temp;
}
// Function to display the linked list
static void printList(Node node)
{
while (node != null )
{
Console.Write(node.data + " " );
node = node.next;
}
}
// Function to check Surpasser Count
static void replaceNodes(Node head)
{
// Pointer used to traverse through
// all the nodes in the list
Node p = head;
// Pointer used to traverse through the right
// elements to count the greater elements
Node x = null ;
// Variable to count the number of
// elements greater than the
// current element on right
int count = 0;
int i;
// Traverse through all the elements
// in the list
while (p != null )
{
count = 0;
i = 0;
// Initialize x to current node
x = p;
// Check or count the number of nodes
// that are greater than the current
// node on right
while (x != null )
{
if (x.data > p.data)
count++;
x = x.next;
}
// Replace the node data with the
// count of elements greater than
// the current element
p.data = count;
p = p.next;
}
}
// Driver code
public static void Main()
{
// Creating the linked list
Node head = newNode(10);
head.next = newNode(12);
head.next.next = newNode(5);
head.next.next.next = newNode(40);
head.next.next.next.next = newNode(21);
head.next.next.next.next.next = newNode(70);
head.next.next.next.next.next.next = newNode(1);
head.next.next.next.next.next.next.next = newNode(49);
head.next.next.next.next.next.next.next.next = newNode(37);
replaceNodes(head);
printList(head);
}
}
/* This code contributed by PrinciRaj1992 */
Выход:
6 5 5 2 3 0 2 0 0

Сложность времени : O (N 2 ), где N - количество узлов в связанном списке.
Вспомогательное пространство : O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter C++

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023