22C:21: Computer Science II: Data Structures
## Quiz 5: October 22, 2004

Write a function that takes a doubly linked list and creates an equivalent
singly linked list.
The function header you should use is the following:
SinglyLinkedList doubleToSingle(DoublyLinkedList L)

For example, if `L` contains three nodes with data 10, 2, and 4 (read
in order from the head of the list to the tail) then the `SinglyLinkedList` that is returned
by the function should also contain three nodes with data 10, 2, and 4 (read
in order from the head of the list).
**Notes:**

- Your function should run in O(n) time, where n is the number of elements in
`L`.
- It is okay for your function to destroy
`L`.
- The function can be written with 5-6 lines of code.

SinglyLinkedList doubleToSingle(DoublyLinkedList L)
{
SinglyLinkedList SL;
SL = new SinglyLinkedList();
while(!L.isEmpty())
SL.addFirst(L.removeLast());
return SL;
}

The above function takes O(n) time because the function calls to `isEmpty()`,
`removeLast()`, and `addFirst` all take O(1) time each.
Note that `removeLast()` takes O(1) time on a doubly linked list, but O(n) time
on a singly linked list with n nodes.
In each execution of the while-loop one node is removed from the doubly linked list and
therefore the while-loop executes n times.

Also note that the order of the elements in preserved in transferring the elements from `L` to
`SL`.