Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Steps
3.2.
Code in C++
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a linked list?
4.2.
Does the linked list have a loop?
4.3.
What are the types of linked lists?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Make a Loop at the K-Th Position in the Linked List

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM
Linked List

Introduction

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. Linked Lists are one of the most fundamental and important data structures having a wide range of applications. Linked Lists are also important from the perspective of interviews as well. 

Problem Statement

Given a linked list and an integer K. Make a loop at the K-th position, i.e. attach the last node of the linked list to the K-th node from the starting of the list.

Examples:

Input1: 4 6 1 3 9 , K=2

 

linked list

 

Output1: 4 6 1 3 9 6

 

linked list
 

Input2: 1 5 6 7 8, K=3

 

linked list

 

Output2: 1 5 6 7 8 6

 

linked list

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

  1. First, reach the K-th node from the starting node of the given linked list.
  2. Save the K-th node’s address in a pointer variable.
  3. Reach the ending node of the linked list.
  4. Attach the ending node with the K-th node of the linked list.

Steps

  1. Declare a curr pointer pointing initially to the head of the linked list.
  2. Run a for loop K-1 times and do curr=curr->next.
  3. Now, the curr pointer is pointing to the K-th node of the linked list. Declare another pointer kth_pos and point it to the K-th node of the linked list, i.e. kth_pos=curr.
  4. Now, Run a while loop till curr->next!=NULL and inside the while loop, perform curr=curr->next.
  5. Now, the curr pointer is pointing to the ending node of the linked list.
  6. Finally, attach the end node to the K-th node of the linked list, i.e. curr->next=kth_pos.
     

Let’s understand the above algorithm with an example:

Input: 4 6 1 3 9, K=3

 

 Initially, the curr pointer is pointing to the head of the given linked list.
 

linked list

The curr pointer reaches the K-th node of the linked list. Now, point this K-th node with another kth_pos pointer.

 

linked list

Move the curr pointer by one step, curr=curr->next.

 

linked list
Move the curr pointer by one step, curr=curr->next.
 

linked list

Now, here curr->next=NULL, it means curr pointer reaches the end node of the linked list.
 

linked list
Finally, attach the end to the K-th node of the linked list, i.e. curr->next=kth_pos.
 

linked list

Code in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    
    int data;

    Node* next;

    Node(int x)
    {
        data = x;
        next = NULL;
    }
};

void makeloop( Node* head, int K)
{
    Node* curr = head;

    for (int i = 1; i < K; i++)
        curr = curr->next;

    Node* kth_pos = curr;

    while (curr->next != NULL)
        curr = curr->next;

    curr->next = kth_pos;
}

void printList( Node* head, int nodes)
{
    Node* curr = head;

    for (int i = 0; i < nodes; i++)
    {
        cout << curr->data << " ";
        curr = curr->next;
    }

}
int count_nodes(Node* head)
{
    Node* curr = head;

    int count = 0;

    while (curr != NULL)
    {
        count++;
        curr = curr->next;
    }

    return count;
}

int main()
{
    Node* head = NULL;

    head = new Node(4);
    head->next = new Node(6);
    head->next->next = new Node(1);
    head->next->next->next = new Node(3);
    head->next->next->next->next = new Node(9);

    int k = 2;

    int nodes = count_nodes(head);

    makeloop(head, k);

    printList(head, nodes + 1);

    return 0;
}

 

Output

4 6 1 3 9 6

Complexity Analysis

Time complexity- The time complexity is O(n), where n is the number of nodes in the given linked list as we are visiting all the nodes.

Space complexity- The space complexity of the above solution is O(1) as we need constant extra space.

Frequently Asked Questions

What is a linked list?

A linked list is a dynamic data structure in which each element (called a node) consists of two components: data and a reference (or pointer) to the next node. A linked list is a collection of nodes, each of which is linked to the next node by a pointer.

Does the linked list have a loop?

A loop in a linked list is a condition that occurs when there is no end to the linked list. When a loop exists in a linked list, the last pointer does not point to the Null as in a singly or doubly linked list or the head of the linked list as in a circular linked list.

What are the types of linked lists?

Types of Linked list

  • Singly Linked list.
  • Doubly Linked list.
  • Circular Linked list.
  • Doubly Circular Linked list.

Conclusion

So, this article discussed the approach to making a loop at the K-th position in the linked list with a complete explanation and its implementation in C++. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Delete Nodes that have a Greater Value on the Right Side in the Linked List
Next article
Identical Linked Lists
Live masterclass