Dada una Lista Vinculada, la tarea es verificar si la Lista Vinculada está ordenada en orden Descendente o no.
Ejemplos:
Input : 8 -> 7 -> 5 -> 2 -> 1 Output : Yes Explanation : In given linked list, starting from head, 8 > 7 > 5 > 2 > 1. So, it is sorted in reverse order Input : 24 -> 12 -> 9 -> 11 -> 8 -> 2 Output : No
Enfoque iterativo: recorrer la lista enlazada de principio a fin. Para cada elemento recién encontrado, marque Node -> datos > Node -> siguiente -> datos . Si es verdadero, haga lo mismo para cada Node; de lo contrario, devuelva 0 e imprima «No».
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
{
int data;
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(int data)
{
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
// Java program to check Linked List is sorted
// in descending order or not
class GFG
{
/* Linked list node */
static class Node
{
int data;
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(int data)
{
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 int data;
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(int data)
{
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
Javascript
<script>
// JavaScript program to recursively check Linked List
// is sorted in descending order or not
/* Linked list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// function to Check Linked List is
// sorted in descending order or not
function isSortedDesc(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);
}
function newNode(data) {
var temp = new Node();
temp.next = null;
temp.data = data;
return temp;
}
// Driver code
var head = newNode(7);
head.next = newNode(5);
head.next.next = newNode(4);
head.next.next.next = newNode(3);
if (isSortedDesc(head) == true) document.write("Yes");
else document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O(N), donde N es la longitud de la lista enlazada.
Enfoque recursivo:
verifique recursivamente ese Node -> datos> Node -> siguiente -> datos , si no, devuelva 0, que es nuestra condición terminada para salir de la recursividad; de lo contrario, llame a la función Check_List recursivamente para el siguiente Node.
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
{
int data;
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(int data)
{
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
// Java program to recursively check Linked List
// is sorted in descending order or not
class GfG {
/* Linked list node */
static class Node
{
int data;
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(int data)
{
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 int data;
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(int data)
{
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
Javascript
<script>
// Javascript program to recursively check Linked List
// is sorted in descending order or not
class Node
{
constructor(data) {
this.next = null;
this.data = data;
}
}
// function to Check Linked List is
// sorted in descending order or not
function isSortedDesc(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));
}
function newNode(data)
{
let temp = new Node(data);
return temp;
}
let head = newNode(7);
head.next = newNode(5);
head.next.next = newNode(4);
head.next.next.next = newNode(3);
if(isSortedDesc(head) == true)
document.write("Yes");
else
document.write("No");
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
Yes
Complejidad de tiempo : O(N) donde N no es ningún Node en la lista enlazada
Espacio Auxiliar: O(n)