We will see the logic to rotate a singly linked list by k nodes. Rotation of linked list can be done in two ways: Clockwise rotation and Anti-clockwise rotation.In this post, we will discuss the clockwise rotation of linked list by k nodes.
In clockwise rotation, remove the root node from start of the linked list and add it to the end of the linked list.
Example:
10 -> 7 -> 76 -> 19 -> 9 -> 57 – >Null
7 -> 76 -> 19 -> 9 -> 57 – > 10 – >Null (After first rotation)
76 -> 19 -> 9 -> 57 – > 10 – > 7 – >Null (After second rotation)
19 -> 9 -> 57 – > 10 – > 7 – > 76 ->Null (After third rotation)
While rotating the linked list, we should keep in mind that API should not create any new object as well as not delete the existing object.Rotation process will just rearrange the links of the nodes. We will write the API which will accept the Integer positive value as number of rotations k and API will rotate the linked list by k nodes. [stextbox id=’info’]Logically, if we rotate the linked list N times where N=size of linked list , we will get the original linked list.Suppose, size of a linked list is 5 and number of rotation is 22, so ideally we should not rotate the linked list 22 times. 22 times rotation will be equivalent to 2 times rotation because after 20th rotation, we will have original linked list.[/stextbox]See the below algorithm and execution process.[Try Yourself]
Algorithm:
- Calculate effective Rotation. effectiveRotation = (numberOfRatation) % (size of linked list) . “%” in JAVA will give the remainder.
- Write a For Loop for effective rotation . for (int i=0 ; i < effectiveRotation ; i++)
- Each loop will be responsible to rotate the linked list by 1 node. Follow the below steps for each loop.
- Declare currentNode =root node.
- update rootNode = currentNode.next.
- Nullify the next node of currentNode.
- Get the last node of the linked list.
- Set the next node of lastNode as currentNode.
Execution Process:
See the below rotate method where input argument is positive integer value and method will rotate the linked list.
package com.study.singlyLinkedList;
public class Node<T> {
private T data ;
private Node<T> node;
public Node(T data) {
this.data = data;
}
public Node<T> getNode() {
return node;
}
public void setNode(Node<T> node) {
this.node = node;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
package com.study.singlyLinkedList;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class SinglyLinkedList<T> {
private int size = 0;
private Node<T> node;
/**
*
* @param numberOfRotataion
*/
public void rotate(int numberOfRotataion) {
if(this.node==null){
return;
}
int effectiveRotation=numberOfRotataion % this.size;
for (int i = 0; i < effectiveRotation; i++) {
Node<T> currentNode=this.node;
this.node=currentNode.getNode();
currentNode.setNode(null);
Node<T> lastNode = getLastNode(this.node);
lastNode.setNode(currentNode);
}
}
/**
* If linked list is sorted(Use sorting of linked list), traverse the linked list from root node
* to till end of the linked list.While traversing, compare each node with next consecutive node
* (because linked list is sorted). If current node and next node value is same then remove the
* next node and point the next pointer of current node to next pointer of deleted node.
*
*/
public void removeDuplicate() {
//If root node is null
if(node ==null) {
return;
}
// size of linked list is 1
if(node.getNode()==null) {
return;
}
// sort the linked list
sort();
Node<T> currentNode=node;
Node<T> nextNode=node.getNode();
while(nextNode != null) {
if(currentNode.getData().equals(nextNode.getData())) {
currentNode.setNode(nextNode.getNode());
nextNode=currentNode.getNode();
size--;
}
else {
currentNode=currentNode.getNode();
nextNode=nextNode.getNode();
}
}
}
/**
* If linked list is unsorted and no sorting method is available, we can use Hashing Technique to remove
* the duplicate nodes. Traverse the linked list from root node to end of the linked list and check if
* current node data is in HashSet. If yes, remove the current node. If no, add the current node data to
* HashSet and shift the pointer to next node
*
*/
public void removeDuplicateUsingHashing() {
//If root node is null
if(node ==null) {
return;
}
// size of linked list is 1
if(node.getNode()==null) {
return;
}
Set<T> hash=new HashSet<>();
Node<T> currentNode=node;
Node<T> previousNode=null;
while(currentNode!=null) {
if(hash.contains(currentNode.getData())) {
Node<T> nextNode=currentNode.getNode();
if(previousNode!=null) {
previousNode.setNode(nextNode);
}
currentNode=nextNode;
size--;
}
else {
hash.add(currentNode.getData());
previousNode=currentNode;
currentNode=currentNode.getNode();
}
}
}
/**
* Sort Linked list using Merge sort algorithm
*
*/
public void sort() {
this.node=sort(this.node);
}
private Node<T> sort(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
// Get the middle of the linked list
Node<T> middleNode=getMiddle(node);
Node<T> rightNode=middleNode.getNode();
// set the next of middle node to null
middleNode.setNode(null);
Node<T> leftNode=node;
// Apply mergeSort on left list
Node<T> sortedLeft = sort(leftNode);
// Apply mergeSort on right list
Node<T> sortedRight = sort(rightNode);
Node<T> sortedList =mergerSortedList(sortedLeft,sortedRight);
return sortedList;
}
/**
* Merge two nodes left node and right node in increasing order
* @param left
* @param right
* @return
*/
private Node<T> mergerSortedList(Node<T> left , Node<T> right){
Node<T> mergedList=null;
if(left== null ) {
return right;
}
if(right== null ) {
return left;
}
if (left.getData().hashCode() <= right.getData().hashCode()) {
mergedList = left;
mergedList.setNode(mergerSortedList(left.getNode(), right));
}
else {
mergedList = right;
mergedList.setNode(mergerSortedList(left, right.getNode()));
}
return mergedList;
}
/**
* Returns the data at middle of the linked list
* @return
*/
public T getMiddle() {
return getMiddle(this.node).getData();
}
/**
*
* @param node
* @return
*/
private Node<T> getMiddle(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
Node<T> fastPointer=node.getNode();
Node<T> slowPointer=node;
// Move fast pointer by two and slow pointer by one
// Finally slow pointer will point to middle node when fast
// pointer will reach at end of the linked list
while (fastPointer !=null) {
fastPointer=fastPointer.getNode();
if(fastPointer!=null) {
slowPointer=slowPointer.getNode();
fastPointer=fastPointer.getNode();
}
}
return slowPointer;
}
/**
* Reverse the linked list by reversing the pointers in reverse direction
*/
public void reverse() {
Node<T> current=this.node;
Node<T> previous=null;
Node<T> next=null;
while(current !=null) {
next = current.getNode();
current.setNode(previous);
previous=current;
current=next;
}
this.node=previous;
}
/**
* Reverse the linked list using stack
*/
public void reverseUsingStack() {
// Push all node to Stack starting from root
Stack<Node<T>> stack=new Stack<Node<T>>();
Node<T> currentNode=this.node;
while(currentNode !=null) {
stack.push(currentNode);
currentNode=currentNode.getNode();
}
// clear the linked list.
this.node = null;
this.size = 0;
//Pop the data from Stack and add it to linked list
if(!stack.empty()) {
Node<T> rootNode=stack.pop();
Node<T> previousNode=rootNode;
currentNode=rootNode;
while(!stack.empty()) {
currentNode = stack.pop();
previousNode.setNode(currentNode);
previousNode=currentNode;
}
previousNode.setNode(null);
this.node=rootNode;
}
}
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
size++;
}
/**
* Add element at first. set the newly created node as root node
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
Node<T> newNode = new Node<T>(data);
if (this.node != null) {
newNode.setNode(this.node);
this.node = newNode;
} else {
this.node = newNode;
}
size++;
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
Node<T> newNode = new Node<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left nose as newly created Node.
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index);
newNode.setNode(rightNode);
leftNode.setNode(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
}
public T get(int index) {
return getNode(index).getData();
}
/**
* Returns the index of data. Index starts from 0 to n. If data not found in
* list, return -1
*
* @param data
* @return
*/
public int indexof(T data) {
Node<T> pointerNode = this.node;
int index = 0;
while (pointerNode != null && pointerNode.getData() != null) {
if (pointerNode.getData().equals(data)) {
return index;
} else {
pointerNode = pointerNode.getNode();
index++;
}
}
return -1;
}
private Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node<T> next(Node<T> node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
/**
* Delete the first occurrence of element from linked list if exists and returns
* true. If data not available , it returns false;
*
* @param data
* @return
*/
public boolean delete(T data) {
if (this.node == null) {
return false;
}
Node<T> pointerNode = this.node;
// If input data is the head of linked list.
if (pointerNode.getData().equals(data)) {
this.node = next(pointerNode);
size--;
return true;
}
int indexofData = indexof(data);
if(indexofData >0 ) {
return deleteByIndex(indexofData);
}
else {
return false;
}
}
/**
* Delete the data by index.
*
* @param index
* @return
*/
public boolean deleteByIndex(int index) {
if (this.node == null) {
return false;
}
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , put head node = Node at index 1.
if (index == 0) {
if(this.node.getNode()!=null) {
this.node = getNode(index + 1);
}else {
this.node=null;
}
size--;
return true;
}
// If index= size -1 means need to delete last node, get the 2nd last node and
// set next node as null.
if (index == this.size - 1) {
getNode(index - 1).setNode(null);
size--;
return true;
}
// if index is in between 0 and size of linked list , set Node of leftNode as
// rightNode
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index + 1);
leftNode.setNode(rightNode);
size--;
return true;
}
/**
* Clear the linked list
*/
public void clear() {
this.node = null;
this.size = 0;
}
@Override
public String toString() {
String represent = "[";
Node<T> nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
/**
* Two linked list is equal when their size is equals and both have similar node structure
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList other = (SinglyLinkedList) obj;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
if (size != other.size)
return false;
return true;
}
}
package com.study.singlyLinkedList;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Integer> linkedList=new SinglyLinkedList<Integer>();
linkedList.add(10);
linkedList.add(7);
linkedList.add(76);
linkedList.add(19);
linkedList.add(9);
linkedList.add(57);
System.out.println("Original List: "+ linkedList);
System.out.println(" ");
linkedList.rotate(3);
System.out.println("Linked List after 3 rotations: "+ linkedList);
System.out.println(" ");
linkedList.rotate(21);
System.out.println("Linked List after 21 rotations: "+ linkedList);
System.out.println(" ");
}
}
Output:
*****************************************************************************************
Original List: [10,7,76,19,9,57]
Linked List after 3 rotations: [19,9,57,10,7,76]
Linked List after 21 rotations: [10,7,76,19,9,57]
*****************************************************************************************
In the above main method, first we are rotating the linked list by 3 nodes. In second rotate method call we are rotating 21 times which is equivalent to 3 times ( 21 % 6[size of linked list]). Finally, the linked list will rotate totally 6 times and result will be same as original list.
We saw the clockwise rotation of linked list. For anti-clockwise rotation, we should remove the last node and add it to the root of the linked list. Try yourself. If finding any difficulty, please post a comment. Happy to hear you 🙂
Hope you like this post. Please leave your comments/suggestions.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list.
- Reverse of Singly Linked List.
- Implementation of Index based Linked List.
- Merge sort for Linked List in Java
- Intersection of two linked lists.
- Iterator for singly linked list java.
