Pass through the list once, copying the data to a malloc()ed array. Free the linked-list. Pass through the array once, in reverse order, copying the data to a new linked-list. Free the array. This algorithm is O(n). The fact that the linked-list exists makes allocating the array resonable.

1. because a linked list can not be traversed backwards, create a simple double-linked list that mimics the original linked list except that each node has knowledge of it's previous node as well as it's next node. 2. maintain three pointers: one pointing to the head element of the new double-linked list, one pointing to the tail element of the new double-linked list, and one as a temporary pointer. 3. working with the double-linked list, assign head to temp, tail to head, temp to tail. 4. increament head one towards tail, decrement tail one towards head. repeat steps 3 and 4 until head is equal to or greater than tail. the double-linked list now contains nodes of the linked list in reverse order. 5. iterate through both linked list and double-linked list while assigning double-linked list nodes to linked list nodes. linked list nodes order now reversed.