how can I reverse my Linked list . I wrote following code but this is giving only first node's data as output

Question

Node *reverse(Node *head)
{
    Node *answer = NULL, *p = head, *address = NULL;

    while (p != NULL)
    {
        address = p;
        address->next = answer;
        answer = address;
        p = p->next;
    }
    return answer;
}

Answer 1

In order to reverse a singly linked list, you need to keep one node in memory to be able to relink backwards.

It could look like this:

Node* reverse(Node* head) {
    if(head) {                               // must have at least one node
        Node* curr = head->next;             // head + 1
        head->next = nullptr;                // this will be the new last node
        Node* next;                          // for saving next while relinking
        while(curr) {                        // while curr != nullptr
            next = curr->next;               // save the next pointer
            curr->next = head;               // relink backwards
            head = curr;                     // move head forward
            curr = next;                     // move curr forward
        }
        // head now points at the new start of the list automatically
    }
    return head;
}

Demo

Answer 2

I wrote following code but this is giving only first node's data as output

Because, in reverse() function, you are breaking the link of first node from rest of the list and returning it.

Look at this part of code:

        address = p;
        address->next = answer;
        answer = address;
        p = p->next;

In first iteration of while loop this is what happening:

Pointer address will point to head of list (as p is initialised with head) and, in the next statement, you are doing address->next = answer (note that answer is initialised with NULL). So, address->next is assigned NULL. Both, pointer p and pointer address are still pointing same node. After this, you are doing p = p->next, this will assign NULL to p because p->next is NULL. As, p is NULL, the while loop condition results in false and loop exits and function end up returning the first node.

You should assign p to its next before assigning answer to address->next, like this:

    while (p != NULL)
    {
        address = p;
        p = p->next;   // moved up
        address->next = answer;
        answer = address;
    }

Suggestion:

In C++, you should use nullptr instead of NULL.

Answer 3

Reversing a linked list, in essence, is pretty much flipping the arrows:

Original: A->B->C->D->null
Intermediate: null<-A<-B<-C<-D
Reversed: D->C->B->A->null

void reverseList(void)
{
    Node *prev = nullptr;
    Node *curr = head;
    while (curr)
    {
        Node *nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }

    head = prev;
}

The crux of the solution will be to use the previous and current node strategy to loop through the list. On lines two and line 3, I set the prev to null and curr to the head respectively. Next, I set the while loop, which will run until curr is equal to null or has reached the end of the list. In the 3rd and 4th lines of the body of the while loop, I set prev to curr and curr to nxt to help me move through the list and keep the traversal going while keeping track of the previous and current nodes.

I am storing the next of the current node in a temporary node nxt since it gets modified later.

Now, curr->next = prev is the statement that does some work. Flipping of the arrows takes place through this statement. Instead of pointing to the next node, we point the next of the current node to the previous node.

Now, we need to take care of the head node only. On the last line, head=prev, prev is the last node in the list. We set the head equal to that prev node in the list, which completes our code to reverse a list.

Suppose you have any trouble visualizing the algorithm. In that case, you even have the privilege to print the data stored in the current and previous nodes after each line in the while loop for a better understanding. Hope this helps getting the gist of how we reverse a linked list.