Given a linked list. Write a C program to reverse it.

Question

Alphonse · Accepted Answer

All the solutions mentioned above require Theta(N) auxiliary space.

To do it with O(1) space in O(N) time, just keep track of the next node's next field. So if the linked list is A -> B -> C -> D, when you're at A, record the fact that C is B's descendent somewhere. Then change the field to be A <- B. Now go to C and record it's descendent. Use the same process until you reach end of list.

L.Severi · Answer

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.

C.W. · Answer

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.

Oracle

Domanda di colloquio di Oracle

Risposte di colloquio

Aziende seguite

Ricerche di lavoro