Find the fractional (or n/k – th) node in linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we have been given a linked list and positive integer k. Our task is to write a function that accepts the head node of the linked list as a parameter and returns the value of the node present at (ceil(n/k))^th position in the linked list.

Here, n is the count of the number of nodes in the linked list.

Problem Statement Understanding

Let’s try to understand the problem with help of examples.

Suppose we are given a linked list


Now according to the problem statement we have to find the node at (ceil(n/k))^th position in the linked list and return its value.

For the above given linked list n = 6, as there are 6 nodes in the linked list, so

• (ceil(n/k)) = (ceil(6/4)) = 2, it means that we have to return the value of 2^nd node of the linked list as output.

Output: B
Explanation: We will return B in output as B is the value of (ceil(n/k))^th node of the above given linked list.

If the linked list is

For the above linked list n = 9 (as there are 9 nodes in the linked list), then the value of (ceil(n/k)) is:

• (ceil(n/k)) = (ceil(9/3)) = 3, so we will return the value of the 3^rd node of the linked list as output.

Output: C

Note: Here in this problem we are considering 1 based indexing.

Some more Examples

Input:

Output: 5

Input:

Output: 60

Input:

Output: 18

Now I think from the above examples the problem is clear, and now we have to think how can we approach it.

Approach 1

A simple approach is:

• First, loop through the linked list to find the count of number of nodes n present in the linked list.
• Then calculate the value of (ceil(n/k)).
• Now starting from the first node of the list traverse to this position given by (ceil(n/k)) and return the data of the node at this position.

Time Complexity: O(n), as we are traversing the complete length of the list.
Space Complexity: O(1)

This approach traverses the linked list 2 times. Let's try to think, can we do better than this? Can we find out the (ceil(n/k))^th node of the linked list in one single traversal?

Let’s see the approach 2 to get the answers to the above questions.

Approach 2

In this approach, we can get the required node by traversing the list once only. The complete algorithm for this approach is explained below.

Algorithm

• If k<=0 or our head==NULL, then return NULL.
• We will take two pointers temp and req_node and initialize temp with head and req_node with NULL.
• For every k jumps of the temp pointer, we will make one jump of the req_node pointer.
• Now when temp will be at NULL, req_node will be at (ceil(n/k))^th node of the linked list.
• Finally, we will return the req_node->data as output.

Dry Run

Code Implementation:

#include 
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* newNode(int data)
{
    Node* new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
Node* fractionalNodes(Node* head, int k)
{
    if (k <= 0 || head == NULL)
        return NULL;

    Node* req_node = NULL;
    
    int i = 0;
    for (Node* temp = head; temp != NULL; temp = temp->next) {

        if (i % k == 0) {

            if (req_node == NULL)
                req_node = head;

            else
                req_node = req_node->next;
        }
        i++;
    }
    return req_node;
}

void printList(Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main(void)
{
    Node* head = newNode(3);
    head->next = newNode(5);
    head->next->next = newNode(7);
    head->next->next->next = newNode(9);
    head->next->next->next->next = newNode(11);
    int k = 2;

    printf("List is ");
    printList(head);

    Node* answer = fractionalNodes(head, k);
    printf("\nFractional node is ");
    printf("%d\n", answer->data);

    return 0;
}

Output

List is 3 5 7 9 11
Fractional node is 7

Time Complexity: O(n), as we are traversing the complete length of the list

So, in this article, you have learnt how to get the value of the node present at (ceil(n/k))^th position in the Linked List. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.