The task is to determine pairs in a doubly-linked list whose sum equal

1.	The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.
Answer» The approach is as FOLLOWS: Two pointer variables are to be initialized to find the possible ELEMENTS in the sorted DOUBLY linked list. Initialize num1 with the head of the doubly linked list,i.e., num1=head, and num2 with the last node of the doubly linked list, i.e., num2=lastNode. If the current sum of num1 and num2 is less than Val, then we advance num1 in the forward direction. If the current total of the num1 and num2 is greater than x, then num2 is moved in the backward direction. When the two POINTERS cross each other (num2->next = num1) or they become equal (num1 == num2), the loop ends. The condition "num1==num2" will handle the CIRCUMSTANCE where no such pairs are present. Implementation: vector<pair<int,int>> sumPair(struct Node head, int val){ // Two pointers are to be set, one to the beginning // and the other to the last of the DLL. struct Node num1 = head; struct Node *num2 = head; while (num2->next != NULL) //to get to the last node num2 = num2->next; vector<pair<int,int>> ans; // The loop ends when two pointers // cross each other or they are equal while (num1 != num2 && num2->next != num1) { if ((num1->value + num2->value) == val) { ans.push_back(make_pair(num1->value,num2->value)); // move num1 in the forward direction num1 = num1->next; // move num2 in the backward direction num2 = num2->prev; } else { if ((num1->value + num2->value) > val) num2 = num2->prev; else num1 = num1->next; } } return ans;} Time Complexity: O(n) Space Complexity: O(1)

The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.

Answer»

The approach is as FOLLOWS:

Two pointer variables are to be initialized to find the possible ELEMENTS in the sorted DOUBLY linked list. Initialize num1 with the head of the doubly linked list,i.e., num1=head, and num2 with the last node of the doubly linked list, i.e., num2=lastNode.
If the current sum of num1 and num2 is less than Val, then we advance num1 in the forward direction. If the current total of the num1 and num2 is greater than x, then num2 is moved in the backward direction.
When the two POINTERS cross each other (num2->next = num1) or they become equal (num1 == num2), the loop ends. The condition "num1==num2" will handle the CIRCUMSTANCE where no such pairs are present.

Implementation:

vector<pair<int,int>> sumPair(struct Node *head, int val){ // Two pointers are to be set, one to the beginning // and the other to the last of the DLL. struct Node *num1 = head; struct Node *num2 = head; while (num2->next != NULL) //to get to the last node num2 = num2->next; vector<pair<int,int>> ans; // The loop ends when two pointers // cross each other or they are equal while (num1 != num2 && num2->next != num1) { if ((num1->value + num2->value) == val) { ans.push_back(make_pair(num1->value,num2->value)); // move num1 in the forward direction num1 = num1->next; // move num2 in the backward direction num2 = num2->prev; } else { if ((num1->value + num2->value) > val) num2 = num2->prev; else num1 = num1->next; } } return ans;}

Time Complexity: O(n)
Space Complexity: O(1)

The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment