Alforithms and data structure

Homework Assignment #4

1. Write a recursive algorithm that receives a reference to the first node

in a singly-linked list and returns a reference to the last node in the

list. What is the worst-case complexity of your algorithm?

2. Write a recursive algorithm that receives a reference to the first node

in a singly-linked list and returns the total number of nodes in the

given list. What is the worst-case complexity of your algorithm?

3. Write a recursive algorithm that receives a reference to the first node

in a singly-linked list , makes a copy of the given list and returns the

reference to the first node of the new list. What is the worst-case

complexity of your algorithm?

4. Write a recursive algorithm that receives a reference to the first node

in a singly-linked list , makes a reverse copy of the given list and

returns the reference to the first node of the new list. What is the

worst-case complexity of your algorithm?

5. Write a non-recursive algorithm that receives a reference to the first

node in a singly-linked list , reverses the links of the given list without

using a stack and returns the reference to the first node of the

reversed list. What is the worst-case complexity of your algorithm?

What is the memory (space) requirement for your algorithm?