JavaScript program to rotate linked list clockwise

The basic structure of a linked list in JavaScript can be created using classes in JavaScript, and nodes can then be moved from one position to another for rotation. In this article, we will learn how to rotate a linked list clockwise in JavaScript programming language. We'll see code for a deeper understanding of these concepts.

In the given problem, we are given a linked list and we have to rotate it in a clockwise manner. This means, we have to put the last element first in every move, if we have to rotate k times, then we have to put the last element before the head or starting node of the linked list. To create the linked list we saw earlier, we need a class to bind data and a pointer to the next element.

Linked list structure

Example

First, we will create a class node that stores the value of the current node and a pointer to the next node. After that, we will create a push function to help create the linked list, and finally, we will create a display function to help print the linked list. Let's look at the code first -

// creating the class for the linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
function display(head){
   var temp = head;
   var values = 0;
   while(temp){   
      values = values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
display(head)

In the above code, we have created a class using the class keyword and created a section using the "this" keyword to store the data and a pointer to the next node in the class constructor.

After that, we define a push function that will take two parameters, the first parameter is the head of the linked list, and the second parameter is the data of the new node we want to add to the linked list. In the function, we create the new node and store the value in it. We check if the head is empty (which means we will add the first element) and then we will simply return the new node, otherwise using a loop we will go to the end of the linked list and add the new node there.

Solution to the problem

After creating the class and defining the required basic functions, we will move to the main function where we will define the function that moves the last k elements to the front of the linked list, which represents the rotation of the linked list. There are two ways to add the last k elements to the first element, which is equivalent to a right rotation of the linked list, for example -

We are given a linked list: 1 -> 2 -> 3 -> 4 -> 5 ->null

We want to rotate the listed links once in a clockwise manner, so it looks like this -

5 -> 1 -> 2 -> 3 -> 4 -> null

Similarly, for 3 rotations of the linked list, the linked list will look like this -

Initially Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null
After the first rotation: 5 -> 1 -> 2 -> 3 -> 4 -> null
After the second rotation: 4 -> 5 -> 1 -> 2 -> 3 -> null
After the third rotation: 3 -> 4 -> 5 -> 1 -> 2 -> null

We have two ways to add the last element in front of the linked list, either one by one, or all at once.

Rotate the linked list one by one

Example

In this method we will go to the last node and then move it to the previous head node and update the head node. Let's take a look at the code first -

// creating the class for linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}

function display(head){
   var temp = head;
   var values = 0
   while(temp){
      values =  values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
function rotate(head, k){
   while(k--){
      var temp = head;
      while(temp.next.next != null){
         temp = temp.next;
      }
      var new_head = temp.next;
      temp.next = null;
      new_head.next = head;
      head = new_head;
   }
   return head;
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
head = rotate(head,3);
display(head);

In the above code, we use the basic function linked list code defined above and just add a new function to rotate the linked list.

In the function rotate, we first use a while loop to traverse the linked list k times, and in each iteration, we reach the penultimate element of the linked list. Then we remove the last element of the linked list from the linked list and place it in front of the head of the linked list. Finally, we return the new header and display the new linked list using the display function.

Time and space complexity

We have moved the linked list k times, and the size of the linked list is N, so the overall time complexity of the program is O(N*K). Additionally, we are not using any extra space, so the space complexity of the program is O(1), which is a constant.

Rotate the linked list once

In the previous code, we added the elements one by one, which took O(N*N) time, so that we can better move the linked list and get the size of the linked list. After that, we will traverse the linked list again and get the last k elements and add them to the front of the linked list, which will make the time complexity of the program O(1).

in conclusion

In this tutorial, we learned how to rotate a linked list clockwise in JavaScript programming language. We have seen the code to understand the concepts in depth. The basic structure of a linked list in JavaScript can be created using classes in JavaScript and then nodes can be moved from one position to another for rotation. The time complexity of the program is O(N*N), which can be further improved to O(N), while the space complexity of the program is O(1).

The above is the detailed content of JavaScript program to rotate linked list clockwise. For more information, please follow other related articles on the PHP Chinese website!