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;
}
You can also try this code with Online C++ Compiler
Run Code
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!