Given a SingleLinkedList, write and test code that rotates an existing Single Linked List by n nodes. Note n can be greater than the count of nodes in the SingleLinkedList.
| Input Parameters |
Expected outputs |
93->16->66->11->77->43->23->9
Rotate by 1 place
|
16->66->11->77->43->23->9->93
|
16->66->11->77->43->23->9->93
Rotate by 3 places
|
77->43->23->9->93->16->66->11
|
77->43->23->9->93->16->66->11
Rotate by 8 places
|
77->43->23->9->93->16->66->11
|
77->43->23->9->93->16->66->11
Rotate by 12 places
|
93->16->66->11->77->43->23->9
|
| The method receives following input parameters: singleLinkedList (SingleLinkedList), nodesToBeRotated (int).
|
| Declare variable named oldFirstNode and set it to singleLinkedList.getFirstNode().
|
| By iterating on the singleLinkedList nodes next links, Find the length of the singleLinkedList and set it in variable listlength and also find reference to last node of SingleLinkedList and set it in variable oldlastNode.
|
| Do following modulo operation to find effective number of node movements to be done:
effectiveMoves = n % listlength
|
| Declare variable named newFirstNode and set it to singleLinkedList.getFirstNode().
|
| Declare variable named newLastNode and set it to null.
|
| To rotate the singleLinkedList, Iterate through the singleLinkedList using a for loop, with loop variable incrementing from 1 to effectiveMoves-1 and execute following steps:
Set variable newLastNode to newFirstNode.
Set variable newFirstNode to newFirstNode.getNextNode().
|
| When above loops completes, newFirstNode will point to the node that is reached by moving forward effectiveMode positions and newLastNode will point to 1 node previous to the newFirstNode.
|
| Set oldLastNode.setNextNode to singleLinkedList.getFirstNode().
|
| Set newLastNode.setNextNode to null.
|
| Set singleLinkedList.setFirstNode to newFirstNode.
|
| Return rotated singleLinkedList.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class SingleLinkedListRotateList {
public SingleLinkedList singleLinkListRotateList(SingleLinkedList singleLinkedList, int nodesToBeRotated) throws Exception{
SingleLinkedListNode oldLastNode=singleLinkedList.getFirstNode();
int singleLinkedListNodeCount=1;
while (oldLastNode.getNextNode() !=null) {
oldLastNode=oldLastNode.getNextNode();
singleLinkedListNodeCount++;
}
int effectiveNodesToBeMoved= nodesToBeRotated % singleLinkedListNodeCount;
if (effectiveNodesToBeMoved<=0) { return singleLinkedList; }
SingleLinkedListNode newFirstNode=singleLinkedList.getFirstNode();
SingleLinkedListNode newLastNode=null;
for (int i=1; i<=effectiveNodesToBeMoved; i++) {
newLastNode=newFirstNode;
newFirstNode=newFirstNode.getNextNode();
}
oldLastNode.setNextNode(singleLinkedList.getFirstNode());
newLastNode.setNextNode(null);
singleLinkedList.setFirstNode(newFirstNode);
return singleLinkedList;
}
public static void main(String[] args) {
try {
SingleLinkedListRotateList singleLinkedListRotateList=new SingleLinkedListRotateList();
SingleLinkedList singleLinkedList=singleLinkedListRotateList.new SingleLinkedList();
SingleLinkedList retVal;
singleLinkedList.addFirst(9);
singleLinkedList.addFirst(23);
singleLinkedList.addFirst(43);
singleLinkedList.addFirst(77);
singleLinkedList.addFirst(11);
singleLinkedList.addFirst(66);
singleLinkedList.addFirst(16);
singleLinkedList.addFirst(93);
singleLinkedList.printSingleLinkList();
System.out.println("Rotate by 1 places");
retVal=singleLinkedListRotateList.singleLinkListRotateList(singleLinkedList,1);
retVal.printSingleLinkList();
System.out.println("Rotate by 3 places");
retVal=singleLinkedListRotateList.singleLinkListRotateList(singleLinkedList,3);
retVal.printSingleLinkList();
System.out.println("Rotate by 8 places");
retVal=singleLinkedListRotateList.singleLinkListRotateList(singleLinkedList,8);
retVal.printSingleLinkList();
System.out.println("Rotate by 12 places");
retVal=singleLinkedListRotateList.singleLinkListRotateList(singleLinkedList,12);
retVal.printSingleLinkList();
System.out.println("Rotate by 16 places");
retVal=singleLinkedListRotateList.singleLinkListRotateList(singleLinkedList,16);
retVal.printSingleLinkList();
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
class SingleLinkedList {
private SingleLinkedListNode firstNode=null;
public SingleLinkedListNode getFirstNode() {
return firstNode;
}
public void setFirstNode(SingleLinkedListNode firstNode) {
this.firstNode = firstNode;
}
public boolean addLast(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
return true;
}
else {
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
currentNode.setNextNode(node);
node.setNextNode(null);
return true;
}
}
public boolean addFirst(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
return true;
}
else {
node.setNextNode(firstNode);
firstNode=node;
return true;
}
}
public boolean add(int data, int pos)
{
int size=getSize();
if ((pos<0) || (pos > size)) { return false;}
if (pos==0) {
addFirst(data);
return true;
}
if (pos==size) {
addLast(data);
return true;
}
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
while (currentNode !=null) {
if ((idx==pos)){
node.setNextNode(prevNode.getNextNode());
prevNode.setNextNode(node);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
}
return false;
}
public int getSize() {
SingleLinkedListNode currentNode=firstNode;
int idx=0;
while (currentNode !=null) {
currentNode=currentNode.getNextNode();
idx++;
}
return idx;
}
public boolean removeFirst() {
if (firstNode == null) { return false; }
if (firstNode.getNextNode()==null) {
firstNode=null;
return true;
}
firstNode=firstNode.getNextNode();
return true;
}
public boolean removeLast() {
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
while (currentNode !=null) {
if (currentNode.getNextNode()==null) {
if (prevNode==null) {
firstNode=null;
return true;
}
prevNode.setNextNode(null);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return false;
}
public boolean remove(int data){
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
while (currentNode !=null) {
if (currentNode.getNodeData() == data) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==null) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return false;
}
public boolean removeAtPos(int pos){
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
while (currentNode !=null) {
if (idx==pos) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==null) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
}
return false;
}
public int get(int idx) {
SingleLinkedListNode currentNode=firstNode;
int currIdx=0;
while (currentNode !=null) {
if (currIdx==idx) {return currentNode.getNodeData();}
currentNode=currentNode.getNextNode();
currIdx++;
}
return Integer.MIN_VALUE;
}
public void traverse() {
SingleLinkedListNode currentNode=firstNode;
while (currentNode !=null) {
System.out.println(currentNode.getNodeData());
currentNode=currentNode.getNextNode();
}
}
// print SingleLinkList
public void printSingleLinkList() throws Exception {
// Case 1: The Linked list is empty !!
if (firstNode == null) { System.out.println("Linked list empty"); return; }
// Case 2: Print LinkedList node by node
SingleLinkedListNode currentNode=firstNode;
System.out.println();
System.out.println("*************************************************************************");
System.out.print("SingleLinkedList nodes: ");
do {
System.out.print(currentNode.getNodeData());
if (currentNode.getNextNode() != null) System.out.print(" -> ");
currentNode=currentNode.getNextNode();
} while( currentNode != null);
System.out.println();
System.out.println("*************************************************************************");
System.out.println();
Thread.sleep(2000);
;
return;
}
}
class SingleLinkedListNode {
private SingleLinkedListNode nextNode=null;
//This is the data stored by Linked list. Replace it by String, array , or any other datatype as per need
private int nodeData=0;
public SingleLinkedListNode getNextNode() {
return nextNode;
}
public void setNextNode(SingleLinkedListNode nextNode) {
this.nextNode = nextNode;
}
public int getNodeData() {
return nodeData;
}
public void setNodeData(int nodeData) {
this.nodeData = nodeData;
}
}
}