Find the Sum of Last N nodes of the Linked List

Given a single linked list, calculate the sum of the last n nodes.

Note: It is guaranteed that n <= number of nodes.

Examples:

Input: Linked List: 5->9->6->3->4->10, n = 3

Output: 17
Explanation: The sum of the last three nodes in the linked list is 3 + 4 + 10 = 17.

Input: Linked List: 1->2, n = 2

Output: 3
Explanation: The sum of the last two nodes in the linked list is 2 + 1 = 3.

Constraints:
1 <= number of nodes, n <= 10⁵
1 <= node->data <= 10³

Approach 01:

class Solution {
public:
    int sumOfLastN_Nodes(Node* head, int n) {
        // Step 1: Reverse the linked list
        Node* previousNode = nullptr;
        Node* currentNode = head;
        Node* nextNode = nullptr;
        int result = 0;
        
        while (currentNode != nullptr) {
            nextNode = currentNode->next;
            currentNode->next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        
        // Now, `previousNode` is the new head (reversed list)

        // Step 2: Sum the first `n` nodes in the reversed list
        currentNode = previousNode;
        while (currentNode != nullptr && n > 0) {
            result += currentNode->data;
            currentNode = currentNode->next;
            n--;
        }
        
        return result;
    }
};

class Solution:
    def sumOfLastN_Nodes(self, head, n):
        # Step 1: Reverse the linked list
        previousNode = None
        currentNode = head
        result = 0
        
        while currentNode is not None:
            nextNode = currentNode.next
            currentNode.next = previousNode
            previousNode = currentNode
            currentNode = nextNode
        
        # Now, `previousNode` is the new head (reversed list)

        # Step 2: Sum the first `n` nodes in the reversed list
        currentNode = previousNode
        while currentNode is not None and n > 0:
            result += currentNode.data
            currentNode = currentNode.next
            n -= 1
        
        return result

Time Complexity

• Reversing the Linked List:

  We traverse the entire linked list once to reverse it. The time complexity for this step is \(O(m)\), where m is the total number of nodes in the linked list.

• Summing the Last N Nodes:

  After reversing the list, we iterate over the first n nodes of the reversed list to sum their values. The time complexity for this step is \(O(n)\), where n is the number of nodes to sum.

• Overall Time Complexity:

  The overall time complexity is \(O(m)\), since reversing the list dominates the time, and n ≤ m.

Space Complexity

• Space for List Reversal:

  We reverse the list in place, so no additional space is required for storing nodes. This operation uses constant space, \(O(1)\), for the pointers (previousNode, currentNode, and nextNode).

• Recursive Call Stack:

  There is no recursion, so no additional space is used for a call stack.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\) since we only use a constant amount of extra space.