Question
In: Computer Science
Find the last node of a linked list of n elements whose index is a multiple...
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);
}
}Solutions
Expert Solution
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))
venereology answered 1 year agoRelated Solutions
3. Find the last node of a linked list of n elements whose index is a...
3. 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 it should return the second 12 (with index 4).
The algorithm should take O(n) time and use O(1) extra space.
Implement the following method in LinkedList.java. public T
lastK(int k)
Assume that a singly linked list is implemented with a header node, but no tail node,...
Assume that a singly linked list is implemented with a header
node, but no tail node, and that it maintains only a pointer to the
header node. Write a class in C++ that includes methods to
a. return the size of the linked list
b. print the linked list
c. test if a value x is contained in the linked list
d. add a value x if it is not already contained in the linked
list
e. remove a value...
Assume that a singly linked list is implemented with a header node, but no tail node,...
Assume that a singly linked list is implemented with a
header node, but no tail node, and that it maintains only a pointer
to the header node. Write a class that includes methods to
a. return the size of the linked list
b. print the linked list
c. test if a value x is contained in the linked list
d. add a value x if it is not already contained in the
linked list
e. remove a value x if...
Data Structures on Java Basic Linked List exercises a. Suppose x is a linked-list node and...
Data Structures on Java
Basic Linked List exercises
a. Suppose x is a linked-list node and not the
last node on the list.
What is the effect of the following code fragment?
x.next = x.next.next
b. Singly Linked List has two private instance
variables first and last as that point to the first and the last
nodes in the list, respectively. Write a fragment of code that
removes the last node in a linked list whose first node is first....
I've provided a Node class that implements a node of a simple singly-linked list (with .value...
I've provided a Node class that implements a node of a
simple singly-linked list (with .value and .next fields), and an
empty LinkedList class. Your task is to implement
LinkedList.sort(l), where given the node l as the head of a
singly-linked list, LinkedList.sort(l) sorts the nodes in the list
into ascending order according to the values in the .value field of
each node.
Your implementation should do an in-place update of
the list. It is ok to use a simple...
Python 3 Function which takes the head Node of a linked list and sorts the list...
Python 3 Function which takes the head Node of a linked list and
sorts the list into non-descending order. PARAM: head_node The head
of the linked list RETURNS: The node at the head of the sorted
linked list. '''
def sort(head_node):
#Code goes here
''' Test code goes here ''
' if __name__ == '__main__':
You are given a reference to the head node of a linked list that stores integers....
You are given a reference to the head node of a linked list that
stores integers. Please print the minimum element in this linked
list. The class ListNode.java contains the description of a single
node in the linked list. It has a num field to store the integer
number and a reference next that points to the next element in the
list. The file MyList.class is a pre-defined java code, that
creates a linked list. The file ListSmallest.java creates an...
Complete the following program:LinkedQueue.zip package jsjf; /** * Represents a node in a linked list. */...
Complete the following
program:LinkedQueue.zip
package jsjf;
/**
* Represents a node in a linked list.
*/
public class LinearNode<T>
{
private LinearNode<T> next;
private T element;
/**
* Creates an empty node.
*/
public LinearNode()
{
next = null;
element = null;
}
/**
* Creates a node storing the specified element.
* @param elem element to be stored
*/
public LinearNode(T elem)...
You are given a reference to the head node of a linked list that stores integers....
You are given a reference to the head node of a linked list that
stores integers. Please print the minimum element in this linked
list. The class ListNode.java contains the description of a single
node in the linked list. It has a num field to store the integer
number and a reference next that points to the next element in the
list. The file MyList.class is a pre-defined java code, that
creates a linked list. The file ListSmallest.java creates an...
You are given a reference to the head node of a linked list that stores integers....
You are given a reference to the head node of a linked list that
stores integers. Please print the minimum element in this linked
list. The class ListNode.java contains the description of a single
node in the linked list. It has a num field to store the integer
number and a reference next that points to the next element in the
list. The file MyList.class is a pre-defined java code, that
creates a linked list. The file ListSmallest.java creates an...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- In the article from Forbes notes that the goal of a leader is not to clone...
- Many people keep time using a 24 hour clock (11 is 11am and 23 is 11pm,...
- UNIX ONLY -- DIFFICULT LAB ASSIGNMENT This is an extremely difficult subject for me. Could you...
- Do you know why your credit card can be refused even though you are profitable?
- The Following Java expression: S/10 * 10 + 10 – S = C Show that this...
- Year Cash Flow 0 −$9,700 1 5,800 2 2,500 3 3,400 &nb
- In a two – story building, an exterior column is to be designed for a service...
ADVERTISEMENT