Problem

Problem: Given a singly linked list and an integer constant k, write a function to find the last element from the beginning whose position satisfies the condition ( n % k = 0 ), where n is the number of elements in the list.

OR

Given a singly linked list, write a function to find the last element from the beginning whose n%k == 0, where n is the number of elements in the list and k is an integer constant. For example, if n = 19 and k = 3 then we should return 18th node.

Examples:

Example 1:

Input: head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: 9 (since 9 is the last node at position 9, which is divisible by 3)

Example 2:

Input: head = [1, 2, 3, 4, 5], k = 2
Output: 4 (since 4 is the last node at position 4, which is divisible by 2)

Example 3:

Input: head = [1, 2, 3, 4, 5], k = 6
Output: None (since there is no position divisible by 6)

Solution

Method 1 - Iteration

  1. Initialize Two Pointers and a Counter:

    • Use a pointer to traverse the list and a counter to keep track of the positions.
    • Maintain a resultNode to store the latest node that satisfies the condition ( n % k = 0 ).

  2. Traverse the List:

    • Iterate through the list, and for each node, check if the current position satisfies the condition ( n % k = 0 ).
    • Update the resultNode whenever the condition is satisfied.

  3. Return the Result:

    • Return the resultNode, which holds the last node whose position satisfies the condition.

Code

Java
public class Solution {
    public ListNode findLastElementDivisibleByK(ListNode head, int k) {
        ListNode resultNode = null;
        ListNode current = head;
        int position = 1;

        while (current != null) {
            if (position % k == 0) {
                resultNode = current;
            }
            current = current.next;
            position++;
        }

        return resultNode;
    }
}
Python
 class Solution:
     def findLastElementDivisibleByK(self, head: ListNode, k: int) -> ListNode:
         result_node = None
         current = head
         position = 1
 
         while current:
             if position % k == 0:
                 result_node = current
             current = current.next
             position += 1
 
         return result_node

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. The list is traversed once.
  • 🧺 Space complexity:  aux space complexity is O(1), since only a constant amount of extra space is used for the pointer.