Find pairs with given sum in doubly linked list | Structure of node of doubly linked list ; Function to find pair whose sum equal to given value x . ; Set two pointers , first to the beginning of DLL and second to the end of DLL . ; To track if we find a pair or not ; The loop terminates when they cross each other ( second . next == first ) , or they become same ( first == second ) ; Pair found ; Move first in forward direction ; Move second in backward direction ; If pair is not present ; A utility function to insert a new node at the beginning of doubly linked list ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . next = None NEW_LINE self . prev = None NEW_LINE DEDENT DEDENT def pairSum ( head , x ) : NEW_LINE INDENT first = head NEW_LINE second = head NEW_LINE while ( second . next != None ) : NEW_LINE INDENT second = second . next NEW_LINE DEDENT found = False NEW_LINE while ( first != second and second . next != first ) : NEW_LINE INDENT if ( ( first . data + second . data ) == x ) : NEW_LINE INDENT found = True NEW_LINE print ( " ( " , first . data , " , " , second . data , " ) " ) NEW_LINE first = first . next NEW_LINE second = second . prev NEW_LINE DEDENT else : NEW_LINE INDENT if ( ( first . data + second . data ) < x ) : NEW_LINE INDENT first = first . next NEW_LINE DEDENT else : NEW_LINE INDENT second = second . prev NEW_LINE DEDENT DEDENT DEDENT if ( found == False ) : NEW_LINE INDENT print ( " No ▁ pair ▁ found " ) NEW_LINE DEDENT DEDENT def insert ( head , data ) : NEW_LINE INDENT temp = Node ( data ) NEW_LINE if not head : NEW_LINE INDENT head = temp NEW_LINE DEDENT else : NEW_LINE INDENT temp . next = head NEW_LINE head . prev = temp NEW_LINE head = temp NEW_LINE DEDENT return head NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT head = None NEW_LINE head = insert ( head , 9 ) NEW_LINE head = insert ( head , 8 ) NEW_LINE head = insert ( head , 6 ) NEW_LINE head = insert ( head , 5 ) NEW_LINE head = insert ( head , 4 ) NEW_LINE head = insert ( head , 2 ) NEW_LINE head = insert ( head , 1 ) NEW_LINE x = 7 NEW_LINE pairSum ( head , x ) NEW_LINE DEDENT