Problem

Given a singly linked list, write a function to find the $\sqrt[]{n}$ element, where n is the number of elements in the list. Assume the value of n is not known in advance.

Follow up

Can you do it in one iteration?

Examples

Input: 1->2->3->4->5->NULL
Output: 2

Input : 10->20->30->40->NULL
Output : 20

Input : 10->20->30->40->50->60->70->80->90->NULL
Output : 30

Solution

Method 1 - Simple

The simple method is to first find the total number of nodes present in the linked list, then find the value of floor(sqrt(n)) where n is the total number of nodes. Then traverse from the first node in the list to this position and return the node at this position.

Method 2 - One Iteration Solution Using Tortoise and Hare Pointers

√n’th node in a singly linked list where n is the number of elements in the list, but n is not known in advance.

  • Use two pointers: one for traversing the list and another for keeping track of the √nth node
  • As we traverse the list, count the number of nodes.
  • Update the √n’th pointer whenever we’ve traversed a new √n’th position
  1. Initialize two counters i and j both to 1 and a pointer sqrtn to NULL to traverse til the required position is reached.
  2. Start traversing the list using head node until the last node is reached.
  3. While traversing check if the value of j is equal to sqrt(i). If the value is equal increment both i and j and sqrtn to point sqrtn->next otherwise increment only i.
  4. Now, when we will reach the last node of list i will contain value of n, j will contain value of sqrt(i) and sqrtn will point to node at jth position.

Code

Java
public class Solution {
    public ListNode findSqrtNthNode(ListNode head) {
        if (head == null) {
            return null;
        }

        int count = 0;
        ListNode current = head;
        ListNode sqrtNthNode = head;

        int sqrtCount = 1; // To keep track of which sqrt position we're at

        while (current != null) {
            count++;
            if (count == sqrtCount * sqrtCount) {
                sqrtNthNode = sqrtNthNode.next;
                sqrtCount++;
            }
            current = current.next;
        }

        return sqrtNthNode;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] arr1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        ListNode head1 = solution.createLinkedList(arr1);

        System.out.println("Original List:");
        solution.printLinkedList(head1);

        ListNode result1 = solution.findSqrtNthNode(head1);
        System.out.println("Sqrt(n)-th node value: " + result1.val);

        int[] arr2 = {1, 2, 3, 4, 5};
        ListNode head2 = solution.createLinkedList(arr2);

        System.out.println("Original List:");
        solution.printLinkedList(head2);

        ListNode result2 = solution.findSqrtNthNode(head2);
        System.out.println("Sqrt(n)-th node value: " + result2.val);
    }
}
Python
class Solution:
    def findSqrtNthNode(self, head: ListNode) -> ListNode:
        if not head:
            return None

        count = 0
        current = head
        sqrt_nth_node = head

        sqrt_count = 1  # To keep track of which sqrt position we're at

        while current:
            count += 1
            if count == sqrt_count * sqrt_count:
                sqrt_nth_node = sqrt_nth_node.next
                sqrt_count += 1
            current = current.next

        return sqrt_nth_node


# Example usage
arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
head1 = create_linked_list(arr1)
solution = Solution()

print("Original List:")
print_linked_list(head1)

result1 = solution.findSqrtNthNode(head1)
print("Sqrt(n)-th node value:", result1.val)

arr2 = [1, 2, 3, 4, 5]
head2 = create_linked_list(arr2)

print("Original List:")
print_linked_list(head2)

result2 = solution.findSqrtNthNode(head2)
print("Sqrt(n)-th node value:", result2.val)

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list.
  • 🧺 Space complexity: O(1), as we use a constant amount of extra space for pointers.