in java

R$-3\mathrm{.}6$ Give an algorithm for finding the second$-$to$-$last node in a singly linked list in which the last node is indicated by a null next reference. Submit your pseudocode in the text entry or PDF$.$

R$-3\mathrm{.}7$ Consider the implementation of CircularlyLinkedList.addFirst, in Code Fragment $3\mathrm{.}16.$ The else body at lines $39$ and $40$ of that method relies on a locally declared variable, newest. Redesign that clause to avoid use of any local variable. Submit the code changes in the text entry or PDF$.$

R$-3\mathrm{.}8$ Describe a method for finding the middle node of a doubly linked list with header and trailer sentinels by $$link hopping,$$ and without relying on explicit knowledge of the size of the list. In the case of an even number of nodes, report the node slightly left of center as the $$middle$.$ Submit your pseudocode in the text entry or PDF$.$

C$-3\mathrm{.}25$ Describe an algorithm for concatenating two singly linked lists. The book provides the following hint: This concatenation operation need not search all of list$1$ and list$2.$

Implement your algorithm in the book's SinglyLinkedList class: Add a concat method to SinglyLinkedList that accepts a SinglyLinkedList and concatenates it to itself. The concat method signature is shown below. Write the body for this method based on your algorithm.

public void concat$($SinglyLinkedList m$)$

For example, assume list$1=(97,98,99)$ and list$2=(1,2,3).$ After calling list$1.$concat$($list$2),$ list$1=(97,98,99,1,2,3).$

The code referenced:

public SinglyLinkedList clone$()$ throws CloneNotSupportedException $\{$

$2//$ always use inherited Object.clone$()$ to create the initial copy

$3$ SinglyLinkedList other $=($SinglyLinkedList$)$ super.clone$()$; $//$ safe cast

$4$ if $($size $>0)\{//$ we need independent chain of nodes

$5$ other.head $=$ new Node$<>($head$.$getElement$(),$ null$)$;

$6$ Node walk $=$ head.getNext$()$; $//$ walk through remainder of original list

$7$ Node otherTail $=$ other.head; $//$ remember most recently created node

$8$ while $($walk $!=$ null$)\{//$ make a new node storing same element

$9$ Node newest $=$ new Node$<>($walk$.$getElement$(),$ null$)$;

$10$ otherTail.setNext$($newest$)$; $//$ link previous node to this one

$11$ otherTail $=$ newest;

$12$ walk $=$ walk.getNext$()$;

$13\}$

$14\}$

$15$ return other;

$16\}$