Given an integer k and a linked list, every node of which consists of a pair of integer variable first and second to hold the data, and a pointer pointing to the next node in the list. The task is to find whether the sum of data variables of any of the nodes is equal to k. If yes then print Yes else print No.
Examples:
Input: (1, 2) -> (2, 3) -> (3, 4) -> (4, 5) -> NULL, k = 5
Output: Yes
For the second node, the sum of data variables is 2 + 3 = 5.Input: (1, 2) -> (2, 3) -> (3, 4) -> (4, 5) -> NULL, k = 15
Output: No
Approach: Traverse the whole linked list until the sum of elements of a node is equal to the key value. When sum of element of a node is equal to key value then print Yes. If there is no such node whose sum of element is equal to the key value then print No.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Represents node of the linked list struct Node { int first; int second; Node* next; }; // Insertion in linked list void insert(Node** head, int f, int s) { Node* ptr = *head; Node* temp = new Node(); temp->first = f; temp->second = s; temp->next = NULL; if (*head == NULL) *head = temp; else { while (ptr->next != NULL) ptr = ptr->next; ptr->next = temp; } } // Function that returns true // if the sum of element in a node = k bool checkK(Node* head, int k) { // Check every node of the linked list while (head != NULL) { // If sum of the data of the current node = k if ((head->first + head->second) == k) return true ; // Get to next node in the list head = head->next; } // No matching node found return false ; } // Driver code int main() { Node* head = NULL; insert(&head, 1, 2); insert(&head, 2, 3); insert(&head, 3, 4); insert(&head, 4, 5); int k = 5; if (checkK(head, k)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach class GfG { // Represents node of the linked list static class Node { int first; int second; Node next; } static Node head = null ; // Insertion in linked list static void insert( int f, int s) { Node ptr = head; Node temp = new Node(); temp.first = f; temp.second = s; temp.next = null ; if (head == null ) head = temp; else { while (ptr.next != null ) ptr = ptr.next; ptr.next = temp; } } // Function that returns true // if the sum of element in a node = k static boolean checkK(Node head, int k) { // Check every node of the linked list while (head != null ) { // If sum of the data of the current node = k if ((head.first + head.second) == k) return true ; // Get to next node in the list head = head.next; } // No matching node found return false ; } // Driver code public static void main(String[] args) { // Node* head = NULL; insert( 1 , 2 ); insert( 2 , 3 ); insert( 3 , 4 ); insert( 4 , 5 ); int k = 5 ; if (checkK(head, k) == true ) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Prerna Saini |
Python3
# Python3 implementation of the approach # Represents node of the linked list class Node: def __init__( self ): self .first = 0 self .second = 0 self . next = None # Insertion in linked list def insert(head, f, s): ptr = head temp = Node() temp.first = f temp.second = s temp. next = None if (head = = None ): head = temp else : while (ptr. next ! = None ): ptr = ptr. next ptr. next = temp return head # Function that returns true # if the sum of element in a node = k def checkK(head, k): # Check every node of the linked list while (head ! = None ): # If sum of the data of the current node = k if ((head.first + head.second) = = k): return True # Get to next node in the list head = head. next # No matching node found return False # Driver code if __name__ = = '__main__' : head = None head = insert(head, 1 , 2 ) head = insert(head, 2 , 3 ) head = insert(head, 3 , 4 ) head = insert(head, 4 , 5 ) k = 5 if (checkK(head, k)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by rutvik_56 |
C#
using System; // c# implementation of the approach public class GfG { // Represents node of the linked list public class Node { public int first; public int second; public Node next; } public static Node head = null ; // Insertion in linked list public static void insert( int f, int s) { Node ptr = head; Node temp = new Node(); temp.first = f; temp.second = s; temp.next = null ; if (head == null ) { head = temp; } else { while (ptr.next != null ) { ptr = ptr.next; } ptr.next = temp; } } // Function that returns true // if the sum of element in a node = k public static bool checkK(Node head, int k) { // Check every node of the linked list while (head != null ) { // If sum of the data of the current node = k if ((head.first + head.second) == k) { return true ; } // Get to next node in the list head = head.next; } // No matching node found return false ; } // Driver code public static void Main( string [] args) { // Node* head = NULL; insert(1, 2); insert(2, 3); insert(3, 4); insert(4, 5); int k = 5; if (checkK(head, k) == true ) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
<script> // Javascript implementation of the approach // Structure of a node of linked list class Node { constructor() { this .first = 0; this .second = 0; this .next = null ; } } // Insertion in linked list function insert( f, s) { var ptr = head; var temp = new Node(); temp.first = f; temp.second = s; temp.next = null ; if (head == null ) head = temp; else { while (ptr.next != null ) ptr = ptr.next; ptr.next = temp; } } // Function that returns true // if the sum of element in a node = k function checkK( head, k) { // Check every node of the linked list while (head != null ) { // If sum of the data of the current node = k if ((head.first + head.second) == k) return true ; // Get to next node in the list head = head.next; } // No matching node found return false ; } // Driver Code var head = null ; insert(1, 2); insert(2, 3); insert(3, 4); insert(4, 5); let k = 5; if (checkK(head, k) == true ) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by jana_sayantn. </script> |
Yes
Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1), as constant space is being used.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!