Linked lists - Data Structures and Problem Solving Using Java - page 648

A linked list contains a cycle if, starting from some node p, following a
sufficient number of next links brings us back to node p . Node p does
not have to be the first node in the list. Assume that you have a linked
list that contains N nodes. However, the value of N is unknown.
a.

17.4

Design an O ( N ) algorithm to determine whether the list contains
a cycle. You may use O ( N ) extra space.

b. Repeat part (a), but use only O (1) extra space. ( Hint: Use two

iterators that are initially at the start of the list, but advance at dif-
ferent speeds.)

One way to implement a queue is to use a circularly linked list. Assume
that the list does not contain a header and that you can maintain one
iterator for the list. For which of the following representations can all
basic queue operations be performed in constant worst-case time? Jus-
tify your answers.
a.

17.5

Maintain an iterator that corresponds to the first item in the list.

b. Maintain an iterator that corresponds to the last item in the list.

Suppose that you have a reference to a node in a singly linked list that is
guaranteed not to be the last node in the list. You do not have references
to any other nodes (except by following links). Describe an O (1) algo-
rithm that logically removes the value stored in such a node from the
linked list, maintaining the integrity of the linked list. ( Hint: Involve the
next node.)

17.6

Suppose that a singly linked list is implemented with both a header and
a tail node. Using the ideas discussed in Exercise 17.6, describe con-
stant-time algorithms to
a.

17.7

Insert item x before position p .

b. Remove the item stored at position p .

IN PRACTICE
17.8

Modify the find routine in the nonstandard LinkedList class to return
the last occurrence of item x .

Modify remove in the nonstandard LinkedList class to remove all occur-
rences of x .

17.9

Suppose that you want to splice part of one linked list into another (a so-
called cut and paste operation). Assume that three LinkedListIterator
parameters represent the starting point of the cut, the ending point of
the cut, and the point at which the paste is to be attached. Assume that
all iterators are valid and that the number of items cut is not zero.

17.10