Last Updated on November 28, 2022 by Prepbytes

In this article, we will see a new coding problem of the linked list i.e.” Create a loop in linked list” A linked list is a linear data structure. 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. Let us understand the problem statement of how to create a loop in linked list.

## How to create a loop in linked list

We will be given a linked list and an integer **K**. We need to attach the last node of the list to the K^{th} node from starting of the list.

To understand this problem statement, let us take an example.

If the given linked list is 3→1→8→2→4→NULL and **K = 3**, then according to the problem statement:

- In the given linked list the third node of the list is
**8**. - So, we need to attach the tail of the list, i.e.,
**4**with**8**. - So, after connecting
**4**to**8**, the list will look like this:

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

## Approach of how to create a loop in linked list

- Firstly, we need to reach the K^{th} node of the list.
- After we reach the K^{th} node, we need to save this node’s address in a pointer variable.
- Then, we need to reach the end of the list and connect it with the K^{th} node (using the pointer variable which we used to store the address of K^{th} node in step 2).

## Algorithm of how to create a loop in linked list

- Initialize a
**count**variable with**1**and a variable**temp**with the first node of the list. -
Run a while loop till the

**count**is less than**K**.- Inside the while loop, in each iteration, increment
**count**by one and move**temp**by one node.

- Inside the while loop, in each iteration, increment
- Save the
**temp**in the**kth_node**variable. - Run a while loop till
**temp**is not NULL.- Inside the while loop, advance
**temp**by one node in each iteration.

- Inside the while loop, advance
- At last, connect
**temp**with**kth_node**i.e.,**temp->next = kth_node**.

### Dry Run of how to create a loop in linked list

## Code Implementation of how to create a loop in linked list

#include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node* next; }; /* Function to make loop at k-th elements of linked list */ struct Node* newNode(int x) { struct Node* node = malloc(sizeof(struct Node*)); node->data = x; node->next = NULL; return node; } void printList(struct Node* head, int total_nodes) { struct Node* curr = head; int count = 0; while (count < total_nodes) { count++; printf("%d ",curr->data); curr = curr->next; } } // this function will create a loop between // the last node and the Kth node void makeloop(struct Node** head_ref, int k) { //initialize 'temp' with the first node struct Node* temp = *head_ref; int count = 1; //run a while loop till 'count' is //less than 'k' while (count < k) { temp = temp->next; count++; } //save the Kth node in a variable struct Node* kth_node = temp; //traverse the list till we reach //the tail node while (temp->next != NULL) temp = temp->next; //join the last node with the Kth node temp->next = kth_node; } int main(void){ struct Node* head = NULL; head = newNode(3); head->next = newNode(1); head->next->next = newNode(8); head->next->next->next = newNode(2); head->next->next->next->next = newNode(4); int k = 3; printf( "\nGiven list\n"); printList(head, 5); makeloop(&head, k); printf("\nModified list\n"); printList(head, 6); return 0; }

#include<bits stdc++.h=""> using namespace std; class Node{ public: int data; Node* next; Node(int x){ data = x; next = NULL; } }; void printList(Node* head, int total_nodes) { Node* curr = head; int count = 0; while (count < total_nodes) { count++; cout << curr->data << " "; curr = curr->next; } } // this function will create a loop between // the last node and the Kth node void makeloop(Node** head_ref, int k) { //initialize 'temp' with the first node Node* temp = *head_ref; int count = 1; //run a while loop till 'count' is //less than 'k' while (count < k) { temp = temp->next; count++; } //save the Kth node in a variable Node* kth_node = temp; //traverse the list till we reach //the tail node while (temp->next != NULL) temp = temp->next; //join the last node with the Kth node temp->next = kth_node; } int main(void){ Node* head = NULL; head = new Node(3); head->next = new Node(1); head->next->next = new Node(8); head->next->next->next = new Node(2); head->next->next->next->next = new Node(4); int k = 3; cout << "\nGiven list\n"; printList(head, 5); makeloop(&head, k); cout << "\nModified list\n"; printList(head, 6); return 0; }

class MakeLoop { static class Node { int data; Node next; } static Node makeloop( Node head_ref, int k) { // traverse the linked list until loop point not found Node temp = head_ref; int count = 1; while (count < k) { temp = temp.next; count++; } // backup the joint point Node joint_point = temp; // traverse remaining nodes while (temp.next != null) temp = temp.next; // joint the last node to k-th element temp.next = joint_point; return head_ref; } // Function to push a node / static Node push( Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Function to print linked list / static void printList( Node head, int total_nodes) { Node curr = head; int count = 0; while (count < total_nodes) { count++; System.out.print(curr.data + " "); curr = curr.next; } } static int countNodes(Node ptr) { int count = 0; while (ptr != null) { ptr = ptr.next; count++; } return count; } // Driver code public static void main(String args[]) { Node head = null; head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); int k = 4; int total_nodes = countNodes(head); System.out.print("\nGiven list\n"); printList(head, total_nodes); head = makeloop(head, k); System.out.print( "\nModified list\n"); printList(head, total_nodes); } }

class Node: def __init__(self, data): self.data = data self.next = None # Function to make loop at k-th elements of #linked list def makeloop(head_ref, k): temp = head_ref count = 1 while (count < k): temp = temp.next count = count + 1 joint_point = temp while (temp.next != None): temp = temp.next temp.next = joint_point return head_ref def push(head_ref, new_data): new_node = Node(new_data) new_node.data = new_data new_node.next = head_ref head_ref = new_node return head_ref def printList( head, total_nodes): curr = head count = 0 while (count < total_nodes): count = count + 1 print(curr.data, end = " ") curr = curr.next if __name__=='__main__': head = None head = push(head, 4) head = push(head, 2) head = push(head, 8) head = push(head, 1) head = push(head, 3) k = 3 print("Given list") printList(head, 5) makeloop(head, k) print("\nModified list") printList(head, 6)

```
Output
Given list
3 1 8 2 4
Modified list
3 1 8 2 4 8
```

**Time Complexity of how to create a loop in linked list:** O(n), n is the total number of nodes in the list.

**Conclusion**

So, in this blog, we have tried to explain how to create a loop in linked list most efficiently with a great explanation and implementation. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

## FAQs related to how to create a loop in linked list

**1. 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.

**2. 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.

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

Types of Linked Lists are:

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