Question about recursive implementation of reversing a singly linked list

I think head, by definition, always points to the first element of a list.

If you want to insert to the end of a linked list in O(1) then keep two references, one to the first element and one to the last element. Then adding to the end is done by following the last reference to the last element, add the new element beyond the last element, update the last reference to point to the new last element.

Inserting to an empty list becomes a special case because you have to set both first and last references not just the last reference. Similarly for deleting from a list with one element.

If you want to the back of a singly linked list, you should keep a reference to the last element. When you want to insert a new element, you create a new link object with the new element as head, the tail of the element you insert it after as the tail, and the new link object as the new tail of the element you insert it afterward. This takes three pointer movements and thus constant time.

For any linked list to have an O(1) insertion time, you have to insert into the front of the list or some other arbitrary location completely disregarding any order. Being a singly linked list means that you can't point to the last element in the list because the list up until the last element will be inaccessible. A fix to this might be as Shannon Severance has stated in that you keep two pointers, a head and a tail. You can use the head to access the elements and the tail to arbitrarily add elements to the list.

Think of it this way:

The reverse of a list consisting of HEAD -> [the rest of the list] is precisely: reverse([the rest of the list]) -> HEAD.

Your base case would be if the list contains a single element. The reverse of such a list is just itself.

Here's an example (using executable pseudo-code, aka Python):

class Node(object):

    def __init__(self, data, next_=None):
        self._data = data
        self._next = next_

    def __str__(self):
        return '[%s] -> %s' % (self._data,
                self._next or 'nil')


def reverse(node):
    # base case
    if node._next is None:
        return node

    # recursive
    head = Node(node._data)     # make a [HEAD] -> nil
    tail_reverse = reverse(node._next)

    # traverse tail_reverse
    current = tail_reverse
    while current._next is not None:
        current = current._next
    current._next = head

    return tail_reverse


if __name__ == '__main__':
    head = Node(0,
            Node(1,
                Node(2,
                    Node(3))))
    print head
    print reverse(head)

Note that this is not in O(1) due to the lack of a last-element reference (only HEAD).