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))


Related 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
ADVERTISEMENT