In: Computer Science
Find the last node of a linked list of n elements whose index is a multiple of k (counted from 0). For example, if the list is 12 → 75 → 37 → 99 → 12 → 38 → 99 → 60 ↓ and k = 4, then you should return the second 12 (with index 4). Your algorithm should take O(n) time and use O(1) extra space. Implement the following method in LinkedList.java.
public T lastK(int k)
LinkedList.java.
public class LinkedList<T> { static class Node<T> { T element; Node<T> next; public Node(T a) { element = a; next = null; } } Node<T> head; // tail public LinkedList() { head = null; } public void insertFirst(T a) { Node<T> newNode = new Node<T>(a); newNode.next = head; head = newNode; // if (tail == null) tail = newNode; } public void insertLast(T a) { if (head == null) { insertFirst(a); return; } Node<T> newNode = new Node<T>(a); Node<T> cur = head; while (cur.next != null) cur = cur.next; newNode.next = null; cur.next = newNode; } public void insertAfter(Node<T> insertionPoint, T a) { Node<T> newNode = new Node<T>(a); newNode.next = insertionPoint.next; insertionPoint.next = newNode; } public void insertBefore(Node<T> insertionPoint, T a) { if (head == insertionPoint) { insertFirst(a); return; } Node<T> cur = head; // at the end of this while loop, // cur will be the node that points to insertionPoint while (cur.next != insertionPoint && cur.next != null) cur = cur.next; Node<T> newNode = new Node<T>(a); newNode.next = cur.next; cur.next = newNode; } public T removeFirst() { if (head == null) { System.out.println("underflow"); return null; } Node<T> temp = head; head = head.next; temp.next = null; // optional but suggested. return temp.element; } public T removeLast() { if (head == null || head.next == null) return removeFirst(); Node<T> secondToLast = head; Node<T> last = secondToLast.next; while (last.next != null) { secondToLast = secondToLast.next; last = last.next; } secondToLast.next = null; // very important: many bugs are from omission of this step. return last.element; } public boolean isEmpty() { return head == null; } public Node<T> search(T a) { Node<T> cur = head; while(cur != null && cur.element != a) cur = cur.next; return cur; } public String toString() { if (head == null) return "The list is empty."; StringBuilder sb = new StringBuilder(); sb.append(head.element); Node<T> cur = head.next; while ( cur != null ) { sb.append(" -> " + cur.element); cur = cur.next; } return sb.toString(); } // reverse the elements in a linked list. public void reverse(Node<T> node) { } public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<Integer>(); System.out.println(list.isEmpty()); list.insertFirst(37); System.out.println(list.isEmpty()); list.insertFirst(99); list.insertFirst(12); list.insertLast(38); System.out.println("After inserting 37, 99, 12 in the front and then 38 at the end, we get"); System.out.println(list); Node<Integer> n99 = list.head; while(n99.next != null) n99 = n99.next; list.insertAfter(n99, 75); System.out.println(list); list.insertBefore(n99, 55); System.out.println(list); System.out.println("delete the last, which is " + list.removeLast()); System.out.println(list); } }
Code for public T lastK(int k)
public T lastK(int k)
{
T value;
int count = 0; // Initialize count
Node<T> current = head; // Initialize current
//to find lendth of linked list
while (current != null)
{
count++;
current = current.next;
}
//find last multiple of index
int index = count/k;
index = index * k;
// Initialize head to current
current = head;
count = 0; // index of Node we are currently looking at
//find element at last multiple of index
while (current != null)
{
if (count == index)
{
break;
}
count++;
current = current.next;
}
//assign element at last multiple of index to value and return
it
value = current.element;
return value;
}
Full code file:
public class Main<T> {
static class Node<T> {
T element;
Node<T> next;
public Node(T a) {
element = a;
next = null;
}
}
Node<T> head; // tail
public Main() {
head = null;
}
public void insertFirst(T a) {
Node<T> newNode = new Node<T>(a);
newNode.next = head;
head = newNode;
// if (tail == null) tail = newNode;
}
public void insertLast(T a) {
if (head == null) {
insertFirst(a);
return;
}
Node<T> newNode = new Node<T>(a);
Node<T> cur = head;
while (cur.next != null)
cur = cur.next;
newNode.next = null;
cur.next = newNode;
}
public void insertAfter(Node<T> insertionPoint, T a) {
Node<T> newNode = new Node<T>(a);
newNode.next = insertionPoint.next;
insertionPoint.next = newNode;
}
public void insertBefore(Node<T> insertionPoint, T a) {
if (head == insertionPoint) {
insertFirst(a);
return;
}
Node<T> cur = head;
// at the end of this while loop,
// cur will be the node that points to insertionPoint
while (cur.next != insertionPoint && cur.next != null)
cur = cur.next;
Node<T> newNode = new Node<T>(a);
newNode.next = cur.next;
cur.next = newNode;
}
public T removeFirst() {
if (head == null) {
System.out.println("underflow");
return null;
}
Node<T> temp = head;
head = head.next;
temp.next = null; // optional but suggested.
return temp.element;
}
public T removeLast() {
if (head == null || head.next == null)
return removeFirst();
Node<T> secondToLast = head;
Node<T> last = secondToLast.next;
while (last.next != null) {
secondToLast = secondToLast.next;
last = last.next;
}
secondToLast.next = null; // very important: many bugs are from omission of this step.
return last.element;
}
public boolean isEmpty() {
return head == null;
}
public Node<T> search(T a) {
Node<T> cur = head;
while(cur != null && cur.element != a)
cur = cur.next;
return cur;
}
public String toString() {
if (head == null) return "The list is empty.";
StringBuilder sb = new StringBuilder();
sb.append(head.element);
Node<T> cur = head.next;
while ( cur != null ) {
sb.append(" -> " + cur.element);
cur = cur.next;
}
return sb.toString();
}
public T lastK(int k)
{
T value;
int count = 0; // Initialize count
Node<T> current = head; // Initialize current
//to find lendth of linked list
while (current != null)
{
count++;
current = current.next;
}
//find last multiple of index
int index = count/k;
index = index * k;
// Initialize head to current
current = head;
count = 0; // index of Node we are currently looking at
//find element at last multiple of index
while (current != null)
{
if (count == index)
{
break;
}
count++;
current = current.next;
}
//assign element at last multiple of index to value and return it
value = current.element;
return value;
}
// reverse the elements in a linked list.
public void reverse(Node<T> node) {
}
public static void main(String[] args) {
Main<Integer> list = new Main<Integer>();
System.out.println(list.isEmpty());
list.insertFirst(12);
list.insertFirst(37);
System.out.println(list.isEmpty());
list.insertFirst(50);
list.insertFirst(99);
list.insertFirst(12);
list.insertLast(38);
System.out.println("After inserting 37, 99, 12 in the front and then 38 at the end, we get");
System.out.println(list);
Node<Integer> n99 = list.head;
while(n99.next != null) n99 = n99.next;
list.insertAfter(n99, 75);
System.out.println(list);
list.insertBefore(n99, 55);
System.out.println(list);
System.out.println("delete the last, which is " + list.removeLast());
System.out.println(list);
System.out.println("element at last multiple of index is "+list.lastK(4));
}
}
Output:
when you pass k=4 list.lastK(4))
when you pass k=2 list.lastK(2))
when you pass k=5 list.lastK(5))