Проверить, отсортирован ли связанный список (итеративный и рекурсивный)

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

Учитывая связанный список, задача состоит в том, чтобы проверить, отсортирован ли связанный список в порядке убывания или нет?

Примеры :

 Ввод: 8 -> 7 -> 5 -> 2 -> 1.
Выход: Да
Объяснение :
В данном связном списке, начиная с головы,
8> 7> 5> 2> 1. Итак, сортировка выполняется в обратном порядке.

Ввод: 24 -> 12 -> 9 -> 11 -> 8 -> 2.
Выход: Нет
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Итерационный подход: просмотрите связанный список от начала до конца. Для каждого вновь обнаруженного элемента проверьте узел -> данные> узел -> следующий -> данные . Если True, сделайте то же самое для каждого узла, иначе верните 0 и выведите «Нет».

C ++

// C++ program to check Linked List is sorted
// in descending order or not
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
struct Node
{
data; int
struct Node* next;
};
// function to Check Linked List is
// sorted in descending order or not
bool isSortedDesc( struct Node *head)
{
if (head == NULL)
return true ;
// Traverse the list till last node and return
// false if a node is smaller than or equal
// its next.
for (Node *t=head; t->next != NULL; t=t->next)
if (t->data <= t->next->data)
return false ;
return true ;
}
Node *newNode( data) int
{
Node *temp = new Node;
temp->next = NULL;
temp->data = data;
}
// Driver program to test above
int main()
{
struct Node *head = newNode(7);
head->next = newNode(5);
head->next->next = newNode(4);
head->next->next->next = newNode(3);
isSortedDesc(head) ? cout << "Yes" :
cout << "No" ;
return 0;
}

Джава

// Java program to check Linked List is sorted
// in descending order or not
class GFG
{
/* Linked list node */
static class Node
{
data; int
Node next;
};
// function to Check Linked List is
// sorted in descending order or not
static boolean isSortedDesc(Node head)
{
if (head == null )
return true ;
// Traverse the list till last node and return
// false if a node is smaller than or equal
// its next.
for (Node t = head; t.next != null ; t = t.next)
if (t.data <= t.next.data)
return false ;
return true ;
}
static Node newNode( data) int
{
Node temp = new Node();
temp.next = null ;
temp.data = data;
return temp;
}
// Driver Code
public static void main(String[] args)
{
Node head = newNode( 7 );
head.next = newNode( 5 );
head.next.next = newNode( 4 );
head.next.next.next = newNode( 3 );
if (isSortedDesc(head))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}
// This code is contributed by 29AjayKumar

Python3

# Python3 program to check Linked List is sorted
# in descending order or not
''' Linked list Node '''
class Node:
def __init__( self , data):
self .data = data;
self . next = next ;
# function to Check Linked List is
# sorted in descending order or not
def isSortedDesc(head):
if (head = = None ):
return True ;
# Traverse the list till last Node and return
# False if a Node is smaller than or equal
# its next.
while (head. next ! = None ):
t = head;
if (t.data < = t. next .data):
return False ;
head = head. next
return True ;
def newNode(data):
temp = Node( 0 );
temp. next = None ;
temp.data = data;
return temp;
# Driver Code
if __name__ = = '__main__' :
head = newNode( 7 );
head. next = newNode( 5 );
head. next . next = newNode( 4 );
head. next . next . next = newNode( 3 );
if (isSortedDesc(head)):
print ( "Yes" );
else :
print ( "No" );
# This code is contributed by 29AjayKumar

C #

// C# program to check Linked List is sorted
// in descending order or not
using System;
class GFG
{
/* Linked list node */
public class Node
{
public data; int
public Node next;
};
// function to Check Linked List is
// sorted in descending order or not
static bool isSortedDesc(Node head)
{
if (head == null )
return true ;
// Traverse the list till last node and
// return false if a node is smaller than
// or equal to its next.
for (Node t = head;
t.next != null ; t = t.next)
if (t.data <= t.next.data)
return false ;
return true ;
}
static Node newNode( data) int
{
Node temp = new Node();
temp.next = null ;
temp.data = data;
return temp;
}
// Driver Code
public static void Main(String[] args)
{
Node head = newNode(7);
head.next = newNode(5);
head.next.next = newNode(4);
head.next.next.next = newNode(3);
if (isSortedDesc(head))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}
// This code is contributed by Rajput-Ji
Выход:
 да

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

Рекурсивный подход:
Рекурсивно проверьте этот узел -> данные> узел -> следующий -> данные. Если нет, верните 0, что является нашим завершенным условием выхода из рекурсии. Else Вызовите функцию Check_List рекурсивно для следующего узла.

C ++

// C++ program to recursively check Linked List
// is sorted in descending order or not
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
struct Node
{
data; int
struct Node* next;
};
// function to Check Linked List is
// sorted in descending order or not
bool isSortedDesc( struct Node *head)
{
// Base cases
if (head == NULL || head->next == NULL)
return true ;
// Check first two nodes and recursively
// check remaining.
return (head->data > head->next->data &&
isSortedDesc(head->next));
}
Node *newNode( data) int
{
Node *temp = new Node;
temp->next = NULL;
temp->data = data;
}
// Driver program to test above
int main()
{
struct Node *head = newNode(7);
head->next = newNode(5);
head->next->next = newNode(4);
head->next->next->next = newNode(3);
isSortedDesc(head) ? cout << "Yes" :
cout << "No" ;
return 0;
}

Джава

// Java program to recursively check Linked List
// is sorted in descending order or not
class GfG {
/* Linked list node */
static class Node
{
data; int
Node next;
}
// function to Check Linked List is
// sorted in descending order or not
static boolean isSortedDesc(Node head)
{
// Base cases
if (head == null || head.next == null )
return true ;
// Check first two nodes and recursively
// check remaining.
return (head.data > head.next.data && isSortedDesc(head.next));
}
static Node newNode( data) int
{
Node temp = new Node();
temp.next = null ;
temp.data = data;
return temp;
}
// Driver program to test above
public static void main(String[] args)
{
Node head = newNode( 7 );
head.next = newNode( 5 );
head.next.next = newNode( 4 );
head.next.next.next = newNode( 3 );
if (isSortedDesc(head) == true )
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}

Python3

# Python3 program to recursively check
# Linked List is sorted in descending
# order or not
# Linked list node
class Node:
def __init__( self , data):
self .data = data
self . next = None
# Function to Check Linked List is
# sorted in descending order or not
def isSortedDesc(head):
# Base cases
if (head = = None or head. next = = None ):
return True
# Check first two nodes and recursively
# check remaining.
return (head.data > head. next .data and
isSortedDesc(head. next ))
def newNode(data):
temp = Node(data)
return temp
# Driver code
if __name__ = = "__main__" :
head = newNode( 7 )
head. next = newNode( 5 )
head. next . next = newNode( 4 )
head. next . next . next = newNode( 3 )
if isSortedDesc(head):
print ( "Yes" )
else :
print ( "No" )
# This code is contributed by rutvik_56

C #

// C# program to recursively check Linked List
// is sorted in descending order or not
using System;
class GfG
{
/* Linked list node */
public class Node
{
public data; int
public Node next;
}
// function to Check Linked List is
// sorted in descending order or not
static bool isSortedDesc(Node head)
{
// Base cases
if (head == null || head.next == null )
return true ;
// Check first two nodes and recursively
// check remaining.
return (head.data > head.next.data &&
isSortedDesc(head.next));
}
static Node newNode( data) int
{
Node temp = new Node();
temp.next = null ;
temp.data = data;
return temp;
}
// Driver code
public static void Main(String[] args)
{
Node head = newNode(7);
head.next = newNode(5);
head.next.next = newNode(4);
head.next.next.next = newNode(3);
if (isSortedDesc(head) == true )
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}
// This code contributed by Rajput-Ji
Выход:
 да

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции 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