InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Given a linked list and a number n, you have to find the sum of the last n nodes of the linked list in a single traversal. Explain your approach in brief. |
|
Answer» The use of two-pointers will REQUIRE a single traversal. We will have to maintain two pointers – reference pointer and main pointer. Both these pointers will be initialized to head. First, the reference pointer will be moved to N nodes from the head, and while traversing, we will keep adding the VALUES and store them into a variable called sum1. Now both the pointers will move simultaneously until the reference pointer reaches the end of the list and while traversing, we will keep adding the values of the nodes. The reference pointer is storing this sum in the variable sum1, and the main pointer will be storing it in sum2. Now, (sum1 – sum2) is the answer, that is the REQUIRED sum of the last n nodes. int getSum(Node* head, int n){ if (n <= 0) return 0; int sum1 = 0, sum2 = 0; struct Node* ptr1 = head; struct Node* ptr2 = head; // the sum of the first n nodes is to be CALCULATED for (ptr1 = head; ptr1 != NULL; ptr1 = ptr1->next;) { sum += ptr1->value; n--; if(n == 0) break; } // now there is a distance of n nodes between the two pointers // move to the end of the linked list while (ptr1 != NULL) { // sum of all the nodes sum1 += ptr1->value; // sum of the first length - n nodes sum2 += ptr2->value; ptr1 = ptr2->next; ptr2 = ptr2->next; } // returning the required sum return (sum1 - sum2);}Time Complexity is O(n) and space complexity is O(1). |
|