I am not really a fan of this question but it seems to be quite a favorite question during technical interview. So, lets discuss reversing a linked-list problem at length.
Basically there are two methods of reversing a linked list – iterative and recursive. Lets discuss the iterative method :
Logic: Iterate trough the linked list. In loop, change next to prev, prev to current and current to next.
private static void reverseIterative()
{
Node prev=null;
Node current= head;
Node next=null;
while(current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
This is simple and has the following complexity :
Time Complexity: O(n)
Space Complexity: O(1)
The recursive method needs a bit of thinking – lets visualize our problem first.
The logic looks like this :
1) Divide the list in two parts – first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer
I think that the recursive solution could be easy as well:
void reverseRecursive(Node **head, Node *prev, Node *curr, Node *next) {
if(!current) { *head = prev; return; }
next = curr->next;
curr->next = prev;
reverseRecursive(head, curr, next, next);
}
void reverse(Node **head) {
reverseRecursive(head, null, *head, null);
{
I think we can remove next pointer
void reverseRecursive(Node **head, Node *prev, Node *curr) {
if(!current) { *head = prev; return; }
next = curr->next;
curr->next = prev;
reverseRecursive(head, curr, next);
}
void reverse(Node **head) {
reverseRecursive(head, null, *head);
{