Count triplets in a sorted doubly linked list whose sum is equal to a given value x | Structure of node of doubly linked list ; Function to count pairs whose sum equal to given ' value ' ; The loop terminates when either of two pointers become null , or they cross each other ( second . next == first ) , or they become same ( first == second ) ; Pair found ; Increment count ; Move first in forward direction ; Move second in backward direction ; If sum is greater than ' value ' move second in backward direction ; Else move first in forward direction ; Required count of pairs ; Function to count triplets in a sorted doubly linked list whose sum is equal to a given value ' x ' ; If list is empty ; Get pointer to the last node of the doubly linked list ; Traversing the doubly linked list ; For each current node ; Count pairs with sum ( x - current . data ) in the range first to last and add it to the ' count ' of triplets ; Required count of triplets ; A utility function to insert a new node at the beginning of doubly linked list ; Allocate node ; Put in the data ; Start with an empty doubly linked list ; Insert values in sorted order
class Node { constructor ( data ) { this . data = data ; this . next = this . prev = null ; } } function countPairs ( first , second , value ) { let count = 0 ; while ( first != null && second != null && first != second && second . next != first ) { if ( ( first . data + second . data ) == value ) { count ++ ; first = first . next ; second = second . prev ; } else if ( ( first . data + second . data ) > value ) second = second . prev ; else first = first . next ; } return count ; } function countTriplets ( head , x ) { if ( head == null ) return 0 ; let current , first , last ; let count = 0 ; last = head ; while ( last . next != null ) last = last . next ; for ( current = head ; current != null ; current = current . next ) { first = current . next ; count += countPairs ( first , last , x - current . data ) ; } return count ; } function insert ( head , data ) { let temp = new Node ( ) ; temp . data = data ; temp . next = temp . prev = null ; if ( ( head ) == null ) ( head ) = temp ; else { temp . next = head ; ( head ) . prev = temp ; ( head ) = temp ; } return head ; } let head = null ; head = insert ( head , 9 ) ; head = insert ( head , 8 ) ; head = insert ( head , 6 ) ; head = insert ( head , 5 ) ; head = insert ( head , 4 ) ; head = insert ( head , 2 ) ; head = insert ( head , 1 ) ; let x = 17 ; document . write ( " " + countTriplets ( head , x ) ) ;