CODEWITHSUNDEEP
cdata-structuresreversesingly-linked-listcircular-list
SRIRAM M
SRIRAM M

Reputation: 11

Can we reverse the elements in a Singly Circular Linked List using only two pointers? Is that possible, efficient and what is the time complexity?

I need to know about only one thing clearly, as I had tried the singly circular linked list reversal using the C language. In that I can't find the correct way and I have no idea regarding this one. Can someone help me to get in a correct way and brief about the time complexity and finally can't we reverse without declaring to NULL?

struct node *Reversescll(struct node *head) {
    if (head == NULL) {
        head->next = head;
        return head;
    }

    struct node *back = NULL;
    struct node *c = head;
    struct node *next = NULL;

    do {
        next = c->next;
        c->next = back;
        back = c;
        c = next;
    } while (c != head);

    head->next = back;
    head = back;
    return head;
}

Upvotes: 1

Views: 233

Answers (1)

chqrlie
chqrlie

Reputation: 144520

Your approach is almost correct, but you have a problem with the empty list: you should just return head or NULL and not dereference head->next when head is NULL.

Here is a corrected version:

struct node *Reversescll(struct node *head) {
    if (head == NULL || head->next == head)
        return head;

    struct node *back = NULL;
    struct node *c = head;

    do {
        struct node *next = c->next;
        c->next = back;
        back = c;
        c = next;
    } while (c != head);

    head->next = back;
    return head;
}

Note that the function always returns its argument.

Now to fully address your question:

Can we reverse the elements in a Singly Circular Linked List using only two pointers?

Yes, it is possible to do it with just 2 extra pointers in addition to the head argument (the above code uses 3 extra pointers):

struct node *Reversescll(struct node *head) {
    if (head == NULL)
        return head;

    struct node *back = NULL;
    while (head->next) {
        struct node *next = head->next;
        head->next = back;
        back = head;
        head = next;
    }
    head->next = back;
    return head;
}

Is that efficient and what is the time complexity?

It is efficient and the complexity is linear, O(n). This is optimal as every node must be changed.

Upvotes: 1

Related Questions