top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Reverse a link-list without any additional pointer?

+3 votes
4,346 views

Is it possible if yes can someone share the code in C?

posted Dec 2, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

If recursion is okay, then u need to walk the list recursively, and then reverse the list as you unwind. This can be accomplished by allowing another parameter to the recursive call to provide the pointer needed to walk through the beginning the list as the recursive calls are unwinding from the end. This implementation uses no extra local variables per recursive call, only the variables provided in the parameters.

void swap_left (node *a, node *b, int tmp) {
    a->data = b->data;
    b->data = tmp;
}

void reverse_recursively (node *cur, node **tail) {
    if (cur) {
        reverse_recursively(cur->next, tail);
        if (*tail) {
            swap_left(cur, *tail, cur->data);
            if (cur != *tail) *tail = (*tail)->next;
            if (cur == *tail) *tail = 0;
        }
    }
}

void reverse (node *list) {
    reverse_recursively(list, &list);
}
answer Dec 11, 2013 by Naveena Garg
Similar Questions
+3 votes

How to delete the node that given as argument in single linked list?
Is there any system call to get prev pointer ?

Note: Here the goal is to delete the address not the node's value

+2 votes

I am looking for sample code which can impress an interviewer.

+4 votes
List => 1 --->  2 --->  3 --->  4 ---> 5 ---> 6
                                      /        \
                                    10          7
                                     \          /
                                      9 <---  8


OURTPUT => 1 --->  2 --->  3 --->  4 ---> 10 ---> 9
                                          /        \
                                        5           8
                                         \          /
                                          6 <---  7
...