How to reverse a singly linked list using only two pointers?

#include <stddef.h>

typedef struct Node {
    struct Node *next;
    int data;
} Node;

Node * reverse(Node *cur) {
    Node *prev = NULL;
    while (cur) {
        Node *temp = cur;
        cur = cur->next; // advance cur
        temp->next = prev;
        prev = temp; // advance prev
    }
    return prev;
}

#include <stdio.h>
#include <malloc.h>

tydef struct node
{
    int info;
    struct node *link;
} *start;

void main()
{
    rev();
}

void rev()
{
    struct node *p = start, *q = NULL, *r;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }

    start = q;
}

curr = head;
prev = NULL;

while (curr != NULL) {
    next = curr->next; // store current's next, since it will be overwritten
    curr->next = prev;
    prev = curr;
    curr = next;
}

head = prev; // update head

class Node {
    Node next;
    int data;

    Node(int item) {
        data = item;
        next = null;
    }
}

public class LinkedList {

    static Node head;

    //Print LinkedList
    public static void printList(Node node){

        while(node!=null){
            System.out.print(node.data+" ");
            node = node.next;
        }
        System.out.println();
    }

    //Reverse the LinkedList Utility
    public static Node reverse(Node node){

        Node new_node = null;

        while(node!=null){

            Node next = node.next;
            node.next = new_node;
            new_node = node;
            node = next;

        }
        return new_node;
    }

    public static void main(String[] args) {

        //Creating LinkedList
        LinkedList.head = new Node(1);
        LinkedList.head.next = new Node(2);
        LinkedList.head.next.next = new Node(3);
        LinkedList.head.next.next.next = new Node(4);

        LinkedList.printList(LinkedList.head);

        Node node = LinkedList.reverse(LinkedList.head);

        LinkedList.printList(node);

    }


}

You can simply reverse a Linked List using only one Extra pointer. And the key to do this is by using a Recursion.

Here is the program in Java.

public class Node {
   public int data;
   public Node next;
}

public Node reverseLinkedListRecursion(Node p) {
    if (p.next == null) {
        head = p;
        q = p;
        return q;
    } else {
        reverseLinkedListRecursion(p.next);
        p.next = null;
        q.next = p;
        q = p;
        return head;
    }
}

// call this function from your main method.
 reverseLinkedListRecursion(head);

As you can see this is a simple example of a head recursion. We have mainly two different kinds of Recursion.

1. Head Recursion:- When the Recursion is the first thing executed by a function.
2. Tail Recursion:- When the Recursion is the last thing executed by a function.

Here the program will keep calling itself Recursively until our Pointer "p" reaches to the last node and then before returning the stack frame we will point head to the last node and the extra Pointer "q" to build the linked list in the backward direction.

Here the Stack Frames will keep on returning until the stack is empty.

Here's a simpler version in python. It does use only two pointers slow & fast

def reverseList(head: ListNode) -> ListNode:

    slow = None
    fast = head
    while fast:  
        node_next = fast.next
        
        fast.next = slow
        slow = fast
            
        fast = node_next
    return slow

Just use an XOR linked list, which is "naturally reversible" in constant time, by just swapping the first and last (head and tail) pointers.

void reverse() noexcept { std::swap(first_, last_); }

I have uploaded a working example as a project on my GitHub.

Solution using 1 variable (Only p):

typedef unsigned long AddressType;

#define A (*( AddressType* )&p )
#define B (*( AddressType* )&first->link->link )
#define C (*( AddressType* )&first->link )

/* Reversing linked list */
p = first;

while( first->link )
{
    A = A + B + C;
    B = A - B - C;
    A = A - B;
    C = A - C;
    A = A - C;
}

first = p;