How can a singly linked list be reversed using only two pointers?

[Rishab7]

I'm curious if there's a specific approach or logic to reverse a singly-linked list using only two pointers. Typically, the reversal involves the use of three-pointers, namely p, q, and r.

struct node {
    int data;
    struct node *link;
};

void reverse() {
    struct node *p = first,
                *q = NULL,
                *r;

    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    first = q;
}

I took reference from this resource. Is there an alternative method for reversing the linked list? What is the most efficient logic for reversing a singly linked list in terms of time complexity?

 

[ChatGPT]

The code you provided is a commonly used approach to reverse a singly-linked list using only two pointers. It works by iteratively updating the pointers to reverse the links between the nodes.

In this approach, we have three pointers, `p`, `q`, and `r`. The variable `p` iterates through the list, while `q` and `r` are used to reverse the links. To reverse the list, `q` becomes the new head of the reversed list, `p` moves to the next node, and the link of `q` is set to `r`. Finally, `r` is updated the point to `q`. The process continues until `p` reaches the end of the original list.

This approach has a time complexity of O(n), where n is the number of nodes in the linked list. It visits each node once, reversing its link in constant time. Therefore, it is an efficient way of reversing a singly-linked list.

Another alternative approach to reversing a singly-linked list is to use recursion. However, this approach typically requires additional space on the stack for recursive function calls, so it might not be as memory efficient as the iterative approach using two pointers.

Here is an example implementation of the recursive approach:

```c
void reverseRecursive(struct node *curr, struct node *prev) {
if (curr == NULL) {
first = prev;
return;
}

reverseRecursive(curr->link, curr);

curr->link = prev;
}

void reverse() {
if (first == NULL)
return;

reverseRecursive(first, NULL);
}
```

In this approach, the `reverse` function initializes the recursive call by passing the head of the list and a `NULL` pointer as the previous node. The `reverseRecursive` function reverses the list by recursively calling itself until it reaches the end of the list (`curr == NULL`). At that point, it sets the new head of the reversed list (`first`) and starts updating the links in reverse order as the recursion unwinds.

Both approaches provide efficient ways to reverse a singly-linked list. The iterative approach with two pointers has the advantage of being memory-efficient without requiring additional space on the stack. However, the choice between these approaches might depend on the specific requirements and constraints of your application.