Dada una lista enlazada individualmente. La tarea es verificar si la diferencia absoluta entre los Nodes consecutivos en la lista enlazada es 1 o no.
Ejemplos:
Entrada: Lista = 2->3->4->5->4->3->2->1->NULL
Salida: SÍ
Explicación: La diferencia entre los Nodes adyacentes en la lista es 1. Por lo tanto, la lista dada es una secuencia de puente.
Entrada: Lista = 2->3->4->5->3->4->NULL
Salida: NO
Enfoque sencillo :
- Tome un puntero temporal para recorrer la lista.
- Inicialice una variable de marca en verdadero, lo que indica que la diferencia absoluta de los Nodes consecutivos es 1.
- Comience a recorrer la lista.
- Compruebe si la diferencia absoluta de Nodes consecutivos es 1 o no.
- En caso afirmativo, continúe con el recorrido; de lo contrario, actualice la variable de indicador a cero y detenga el recorrido.
Bandera de regreso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if absolute difference
// of consecutive nodes is 1 in Linked List
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node {
int data;
struct Node* next;
};
// Utility function to create a new Node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to check if absolute difference
// of consecutive nodes is 1 in Linked List
bool isConsecutiveNodes(Node* head)
{
// Create a temporary pointer
// to traverse the list
Node* temp = head;
// Initialize a flag variable
int f = 1;
// Traverse through all the nodes
// in the list
while (temp) {
if (!temp->next)
break;
// count the number of jumper sequence
if (abs((temp->data) - (temp->next->data)) != 1) {
f = 0;
break;
}
temp = temp->next;
}
// return flag
return f;
}
// Driver code
int main()
{
// creating the linked list
Node* head = newNode(2);
head->next = newNode(3);
head->next->next = newNode(4);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(4);
head->next->next->next->next->next = newNode(3);
head->next->next->next->next->next->next = newNode(2);
head->next->next->next->next->next->next->next = newNode(1);
if (isConsecutiveNodes(head))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if absolute difference
// of consecutive nodes is 1 in Linked List
class GFG
{
// A linked list node
static class Node
{
int data;
Node next;
};
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to check if absolute difference
// of consecutive nodes is 1 in Linked List
static int isConsecutiveNodes(Node head)
{
// Create a temporary pointer
// to traverse the list
Node temp = head;
// Initialize a flag variable
int f = 1;
// Traverse through all the nodes
// in the list
while (temp != null)
{
if (temp.next == null)
break;
// count the number of jumper sequence
if (Math.abs((temp.data) - (temp.next.data)) != 1)
{
f = 0;
break;
}
temp = temp.next;
}
// return flag
return f;
}
// Driver code
public static void main(String[] args)
{
// creating the linked list
Node head = newNode(2);
head.next = newNode(3);
head.next.next = newNode(4);
head.next.next.next = newNode(5);
head.next.next.next.next = newNode(4);
head.next.next.next.next.next = newNode(3);
head.next.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next.next = newNode(1);
if (isConsecutiveNodes(head) == 1)
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to check if absolute difference
# of consecutive nodes is 1 in Linked List
import math
# A linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Utility function to create a new Node
def newNode(data):
temp = Node(data)
temp.data = data
temp.next = None
return temp
# Function to check if absolute difference
# of consecutive nodes is 1 in Linked List
def isConsecutiveNodes(head):
# Create a temporary pointer
# to traverse the list
temp = head
# Initialize a flag variable
f = 1
# Traverse through all the nodes
# in the list
while (temp):
if (temp.next == None):
break
# count the number of jumper sequence
if (abs((temp.data) -
(temp.next.data)) != 1) :
f = 0
break
temp = temp.next
# return flag
return f
# Driver code
if __name__=='__main__':
# creating the linked list
head = newNode(2)
head.next = newNode(3)
head.next.next = newNode(4)
head.next.next.next = newNode(5)
head.next.next.next.next = newNode(4)
head.next.next.next.next.next = newNode(3)
head.next.next.next.next.next.next = newNode(2)
head.next.next.next.next.next.next.next = newNode(1)
if (isConsecutiveNodes(head)):
print("YES")
else:
print("NO")
# This code is contributed by Srathore
C#
// C# program to check if absolute difference
// of consecutive nodes is 1 in Linked List
using System;
public class GFG
{
// A linked list node
public class Node
{
public int data;
public Node next;
};
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to check if absolute difference
// of consecutive nodes is 1 in Linked List
static int isConsecutiveNodes(Node head)
{
// Create a temporary pointer
// to traverse the list
Node temp = head;
// Initialize a flag variable
int f = 1;
// Traverse through all the nodes
// in the list
while (temp != null)
{
if (temp.next == null)
break;
// count the number of jumper sequence
if (Math.Abs((temp.data) - (temp.next.data)) != 1)
{
f = 0;
break;
}
temp = temp.next;
}
// return flag
return f;
}
// Driver code
public static void Main(String[] args)
{
// creating the linked list
Node head = newNode(2);
head.next = newNode(3);
head.next.next = newNode(4);
head.next.next.next = newNode(5);
head.next.next.next.next = newNode(4);
head.next.next.next.next.next = newNode(3);
head.next.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next.next = newNode(1);
if (isConsecutiveNodes(head) == 1)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to check if absolute difference
// of consecutive nodes is 1 in Linked List
// A linked list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Utility function to create a new Node
function newNode( data)
{
var temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to check if absolute difference
// of consecutive nodes is 1 in Linked List
function isConsecutiveNodes( head)
{
// Create a temporary pointer
// to traverse the list
var temp = head;
// Initialize a flag variable
let f = 1;
// Traverse through all the nodes
// in the list
while (temp != null)
{
if (temp.next == null)
break;
// count the number of jumper sequence
if (Math.abs((temp.data) - (temp.next.data)) != 1)
{
f = 0;
break;
}
temp = temp.next;
}
// return flag
return f;
}
// Driver Code
// creating the linked list
var head = newNode(2);
head.next = newNode(3);
head.next.next = newNode(4);
head.next.next.next = newNode(5);
head.next.next.next.next = newNode(4);
head.next.next.next.next.next = newNode(3);
head.next.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next.next = newNode(1);
if (isConsecutiveNodes(head) == 1)
document.write("YES");
else
document.write("NO");
// This code is contributed by jana_sayantan.
</script>
Producción:
YES
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)