Given a Singly Linked List. The task is to check if the absolute difference between the consecutive nodes in the linked list is 1 or not.
Examples:
Input : List = 2->3->4->5->4->3->2->1->NULL
Output : YES
Explanation : The difference between adjacent nodes in the list is 1. Hence the given list is a Jumper Sequence.Input : List = 2->3->4->5->3->4->NULL
Output : NO
Simple Approach:
- Take a temporary pointer to traverse the list.
- Initialize a flag variable to true which indicates that the absolute difference of consecutive nodes is 1.
- Start traversing the list.
- Check if the absolute difference of consecutive nodes is 1 or not.
- If Yes then continue traversal otherwise update flag variable to zero and stop traversing any further.
Return flag.
Below is the implementation of the above approach:
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 nodestruct Node { int data; struct Node* next;};// Utility function to create a new NodeNode* 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 Listbool 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 codeint 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 Listclass GFG {// A linked list nodestatic class Node { int data; Node next;};// Utility function to create a new Nodestatic 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 Liststatic 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 codepublic 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 Listimport math# A linked list nodeclass Node: def __init__(self, data): self.data = data self.next = None# Utility function to create a new Nodedef 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 Listdef 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 codeif __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 Listusing System; public class GFG { // A linked list nodepublic class Node { public int data; public Node next;}; // Utility function to create a new Nodestatic 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 Liststatic 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 codepublic 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 nodeclass Node { constructor() { this.data = 0; this.next = null; } } // Utility function to create a new Nodefunction 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 Listfunction 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 listvar 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> |
Output
YES
Complexity Analysis:
- Time Complexity: O(n) //since only one traversal of the linked list is enough to perform all operations hence the time taken by the algorithm is linear
- Auxiliary Space: O(1) // since no extra array is used so the space taken by the algorithm is constant
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
