Reverse singly linked list

[merlinf]

Hello everyone, I have an assignment that I must reverse a singly linked list, and I tried to search on the Internet and found this code but I really don't understand the algorithm. I really want to understand because it seems efficient. Can anyone help me explain it?

  // Recursive C++ program to reverse
// a linked list
#include <iostream>
using namespace std;

/* Link list node */
struct Node {
	int data;
	struct Node* next;
	Node(int data)
	{
		this->data = data;
		next = NULL;
	}
};

struct LinkedList {
	Node* head;
	LinkedList()
	{
		head = NULL;
	}

	Node* reverse(Node* head)
	{
		if (head == NULL || head->next == NULL)
			return head;

		/* reverse the rest list and put
		the first element at the end */
		Node* rest = reverse(head->next);
		head->next->next = head;

		/* tricky step -- see the diagram */
		head->next = NULL;

		/* fix the head pointer */
		return rest;
	}

	/* Function to print linked list */
	void print()
	{
		struct Node* temp = head;
		while (temp != NULL) {
			cout << temp->data << " ";
			temp = temp->next;
		}
	}

	void push(int data)
	{
		Node* temp = new Node(data);
		temp->next = head;
		head = temp;
	}
};

/* Driver program to test above function*/
int main()
{
	/* Start with the empty list */
	LinkedList ll;
	ll.push(20);
	ll.push(4);
	ll.push(15);
	ll.push(85);

	cout << "Given linked list\n";
	ll.print();

	ll.head = ll.reverse(ll.head);

	cout << "\nReversed Linked list \n";
	ll.print();
	return 0;
}

[DizzyDon]

Node* reverse(Node* head)
{
    // If the list is empty or only has one element
    // then its reverse is itself.
    if (!head || !head->next)
        return head;

    // Call reverse recursively to reverse all but the first element.
    Node* rest = reverse(head->next);

    // Assuming reverse(head->next) returns the list
    // from the second element to the end, reversed, then
    // head->next was the element after head but is now
    // the last element. Setting it's next member to head
    // puts head at the end of the list.
    head->next->next = head;

    // head's next pointer needs to be nulled since it's
    // the last element now.	
    head->next = nullptr;

    // rest is the node that used to be last but is now first
    return rest;
}

It's probably kind of inefficient since it recurses a level for every element of the list. 1000 elements, 1000 levels of recursion. That is a lot of extra memory for no real gain since it's simple to reverse a list non-recursively:

void reverse() {
    Node* prev = nullptr;
    for (Node *node = head; node; ) {
        Node *next = node->next;
        node->next = prev;
        prev = node;
        node = next;
    }
    head = prev;
}

There may be a way to rewrite the recursive version that takes advantage of tail-recursion.

[jonnin]

pop the top and insert it into a new list at the top

1 - 2 -3 -4
pop 1 off, insert
1
pop 2 off, insert
2-1
3-2-1
4-3-2-1
... no iterating through the list at all. No recursion, just one while loop until the original list is empty.

That, recursively, just becomes a loop replacement via recursion ... and probably your loop can do similar.. can you write a recursive function that just loops, nothing else really, like a while loop?