JAVA

Create one final method rotate() for MyLinkedList. This method should take 1 integer argument rot that determines the number of positions to rotate each element in the list. We have done this before for arrays and for dynamic arrays. Some of the code you will need is in those earlier exercise source files on Canvas, specifically the calculation for the exact shift to complete positive number. Once you know the exact shift, you should be able to complete the rotate as a linear operation, completing in one pass through the linked list. HINT: consider using fast/slow pointers to assist in completing.

Example: For the list [5, 4, 3, 8, 1, 9] and shift of 2, result is [1, 9, 5, 4, 3, 8]

Example: For the list [5, 4, 3, 8, 1, 9] and shift of -2, result is [3, 8, 1, 9, 5, 4]

Example: For the list [5, 4, 3, 8, 1, 9] and shift of 37, result is [9, 5, 4, 3, 8, 1]

Example: For the list [5, 4, 3, 8, 1, 9] and shift of -37, result is [4, 3, 8, 1, 9, 5]

PreviousNext

MyLinkedList.java Code

import java.util.Arrays;

/** * */ public class MyLinkedList { private int size; // keeps track of the number of elements private Node head; // reference to the first node /** * */ public MyLinkedList() { head = null; size = 0; } /** * Node is identical to ListNodeInteger * Use inner class since node without list is not useful */ private class Node { public T data; public Node next; public Node(T data) { this.data = data; this.next = null; } public Node(T data, Node next) { this.data = data; this.next = next; } public String toString() { return "Node(" + data.toString() + ")"; } } public boolean add(T element) {

if (head==null) { head = new Node(element); } else { Node node = head; for (; node.next != null; node=node.next); node.next = new Node(element); } size++; return true; } public void add(int index, T element) { if (index == 0) { head = new Node(element, head); } else { Node node = getNode(index-1); node.next = new Node(element, node.next); } size++; } public void clear() { head = null; size = 0; } public boolean contains(T obj) { return indexOf(obj) != -1; } public T get(int index) { Node node = getNode(index); return node.data; } /** Returns the node at the given index. * @param index * @return */ private Node getNode(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(); } Node node = head; for (int i=0; i