top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Reverse node of loop of link list ??

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


OURTPUT => 1 --->  2 --->  3 --->  4 ---> 10 ---> 9
                                          /        \
                                        5           8
                                         \          /
                                          6 <---  7
posted Nov 11, 2013 by Anuj Yadav

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

1 Answer

0 votes

I guess this is the correct output for that is

OUTPUT => 1 ---> 2 ---> 3 ---> 4 ---> 5 ---> 10 ---> 9 ---> 8 ---> 7 ---> 6 ---> [[Back to 4]]

If that is the case then first

Detect loop size in linked list by using Floyd’s Cycle detection algorithm i.e, create 2 pointers one fast and other slow pointing to start of node every time you run one iteration fast will move 2 points ahead and slow will move 1 when two pointers point to same node break.
Now fix one pointer and move other to detect the length of cycle, let it be n

Now we need to find starting point of cycle this can be done by pointing one at start and other at n nodes ahead then when two points point to same node it will be start of cycle..

Now if we reverse this circular linked list i.e, cycle we are done..
Code to reverse circular linked list

void reverse(Node** headRef)
{
    Node* result = NULL;
    Node* current = *headRef;
    Node* next;

    while (current != NULL)
    {
        next = current->next; // tricky: note the next node
        current->next = result; // move the node onto the result
        result = current;
        current = next;
        if (current == *headRef)
        {
            break;
        }
    }
    (*headRef)->next = result;
    *headRef = result;
}

Credits to reverse circular linked list : Circular Link List

answer Nov 24, 2013 by Raghu
Similar Questions
+3 votes

List => 1 2 3 4 5 6 7 8 9

N=3 Out Put => 1 2 3 6 5 4 7 8 9
N=4 Out Put => 1 2 6 5 4 3 7 8 9
N=5 Out Put => 1 2 7 6 5 4 3 8 9

+3 votes

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

...