Theory of computation Number 4. Please answer no. 4 with explanation please Numb
ID: 3734948 • Letter: T
Question
Theory of computation
Number 4. Please answer no. 4 with explanation please
Number 4. Please answer no. 4 with explanation please publle Int size) i int count 0; NodecEswalkhead; whlle (walk null) count++ walk walk, getNext(); return count; De V bly din.us+--we ca-move. Describe a method for finding the middle node of a doubly linked list with header and trailer sentinels by "link hopping" and without of the list. In the case of an even number of nodes, report the node slightly left of center as the "middie: What is the running time of this method Solution relying on explicit knowledge of the size No S Consider a combined search from both ends. Also, recall that a link hop is an assign- ment of the form "p p.getNext0:" or "p- p.getPrevo: The following method runs in O(n) time. nte at valve private NodecES midie { 7 wret private Node middle () if (size0) throw new IllegalState Exception (list must be nonempty ): NodecE> middle-header. getNexfO:> (antay in). NodecE> partner trailer. getPrev(); while (middle te partner getNext() !'partner') { middle middle.getNext ) partner partner. getPrev); return middle; 4. Give an algorithm for finding the in-to-last node in a singly linked list in which the last node is indicated by a null next reference.
Explanation / Answer
Please find my answer:
Method:
1) Calculate the length of Linked List. Let the length be len.
2) Print the (len – n + 1)th node from the begining of the Linked List.
/* Function to get the nth node from the last of a
linked list */
void NthFromLast(int n)
{
int len = 0;
Node<E> temp = head;
// 1) count the number of nodes in Linked List
while (temp != null)
{
temp = temp.getNext();
len++;
}
// check if value of n is not more than length of
// the linked list
if (len < n) {
System.out.println(n+" is more than length");
return;
}
temp = head;
// 2) get the (n-len+1)th node from the begining
for (int i = 1; i < len-n+1; i++)
temp = temp.getNext();
System.out.println(temp);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.