# Make a loop at the K-Th position in the Linked list

## Introduction to the 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

Output1: 4 6 1 3 9 6

Input2: 1 5 6 7 8, K=3

Output2: 1 5 6 7 8 6

## Approach

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

### Steps

- Declare a curr pointer pointing initially to the head of the linked list.
- Run a for loop K-1 times and do curr=curr->next.
- 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.
- Now, Run a while loop till curr->next!=NULL and inside the while loop, perform curr=curr->next.
- Now, the curr pointer is pointing to the ending node of the linked list.
- 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.

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

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

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

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

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

### 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- **It 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

**Q1.** What is a linked list?

**Ans:** 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.

**Q2.** Does the linked list have a loop?

**Ans: ** 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.

**Q3.** What are the types of linked lists?

**Ans: **Types of Linked list

- Singly Linked list.
- Doubly Linked list.
- Circular Linked list.
- Doubly Circular Linked list.

## Key Takeaways

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

If you are a beginner, interested in coding and want to learn DSA, you can look for our__ guided path for DSA__, which is free!

In case of any comments or suggestions, feel free to post them in the comments section.

Comments

## No comments yet

## Be the first to share what you think