Find the Sum of Last N nodes of the Linked List

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Sum last n nodes of linked list. Two-pointer with gap n, or recursive.

Algorithm

1Two pointers: advance first pointer n steps. Then advance both until first reaches end. Sum from second pointer.

Common Pitfalls

•Classic sliding window for linked list. Or convert to array, sum last n elements. O(n).

Find the Sum of Last N nodes of the Linked List.java

Java

// Approach: Two-pass or two-pointer technique. Find the (total - N + 1)-th node and sum from there.
// Time: O(n) Space: O(1)
class Solution {

    // Return the sum of last k nodes
    public int sumOfLastN_Nodes(Node head, int n) {
        Node fast = head;
        Node slow = head;
        int sum = 0;
        int count = 0;
        while (fast != null) {
            sum = sum + fast.data;
            fast = fast.next;
            if (count >= n) {
                sum = sum - slow.data;
                slow = slow.next;
            }
            count++;
        }
        return sum;
    }
}

Was this solution helpful?