Homework 2: LinkedLists

Question 1:

Given a singly linked list head node and int position, delete the node at the given position, and return the head

node. The head node is at position 0. If the linked list is empty after you delete, return null.

Question 2:

Given the pointer to the head node of a doubly linked list, reverse the order of its nodes in place (this phrase

means the algorithm doesnt use any extra space. In this context, think of the references the doubly linked list

has). Your method will return the head of the reversed list.

Question 3:

Implement a doubly linked list class. Its Nodes store int values. The class has the following methods:

void addFirst(int value), void addLast(int value), Node removeFirst(), Node removeLast(), int size(), boolean

isEmpty(). Those operations should have constant time complexity. Then, implement int equals(Node other)

method in the class, itll receive the head of another doubly linked list as input, then return 1 if both lists have

the same values at the same order, else return 0.

Question 4:

Implement a circular linked list that has methods as follows: getLastElement, size, isEmpty, removeFirst.

Question 5:

Given the head of a sorted linked list, implement a method that inserts a number at the right position so that

the list stays sorted.

Question 6:

Given the head of a linked list, implement a method that detects if the linked list has a cycle or not (note: if the

list has a cycle itll be infinite)