Make loop at K-Th position in the Linked List

Problem Statement

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.

Problem Statement Understanding:

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

1) Firstly, we need to reach the K^{th} node of the list.
2) After we reach the K^{th} node, we need to save this node’s address in a pointer variable.
3) 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

1) Initialize a count variable with 1 and a variable temp with the first node of the list.
2) 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.
    3) Save the temp in the kth_node variable.
    4) Run a while loop till temp is not NULL.
  • Inside the while loop, advance temp by one node in each iteration.
    5) At last, connect temp with kth_node i.e., temp->next = kth_node.

Dry Run


Code Implementation

#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: O(n), n is the total number of nodes in the list
[forminator_quiz id=”5836″]

So, in this blog, we have tried to explain how you can make a loop at $K^{th}$ position in the linked list most optimally. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *