Consider the problem of reversing a singly linked list. To take an example, given the linked list below, 

the reversed linked list should look like 

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

A.

The best algorithm for the problem takes θn time in the worst case.

B.

The best algorithm for the problem takes θnlogn time in the worst case.

C.

The best algorithm for the problem takes θn2 time in the worst case.

D.

It is not possible to reverse a singly linked list in O(1) space.

Solution:

We can reverse the singly linked list in θn time in the worst case with O(1) space complexity using temporary variables.

Algorithm for reversing a singly linked list

struct node *reverseSinglyLinkedList(struct node *head) {
    if (head == NULL) return NULL;
    if (head->next == NULL) return head;
    struct node *temp1 = head->next;
    struct node *temp2 = temp1->next;
    head->next = NULL;
    do {
        temp1->next = head;
        head = temp1;
        temp1 = temp2;
        if (temp1) {
            temp2 = temp1->next;
        }
    } while (temp1);
    return head;
}