Change the order of nodes in a single-linked list

Question

Say we have a list 1-2-3-4-5 (values of list can be without order, for example 2-4-5-3-1);
The task is to reorder nodes of list (not values) in the way like this: 1-5-2-4-3.
I wrote the function that uses 2 temporary variables and 1 pointer. But the problem is I don't know how to set the "next" pointer in penultimate node to "NULL" without defining the second temporary pointer in function. Is there a more efficient way to do this?

void Swap(Node* begin)
{
    if (begin->next != NULL || begin->next->next != NULL)
    {
        Node temp1 = *begin; //this variable is used for iteration
        Node* temp2 = begin; //pointer to the target node
        Node prev; //get the adress of last node
        while (temp1.next != NULL)
        {
            prev = temp1;
            temp1 = *temp1.next;
        }
        prev.next->next = temp2->next;
        temp2->next = prev.next;
        Swap(prev.next->next);
    }

}

Answer 1

You can use this algorithm: o(n) time complexity

1. Count the no of nodes(n) in list.

2. Put the last n/2 nodes in a stack.

3. Start traversing the list from the starting.

4. For each traversed element, pop the element from stack and make it the next element of the traversed element.

5. Do this until stack gets empty.

6. Keep in mind to change the last node next pointer to NULL.

   (In case of odd count you have to traverse one more element even if stack is empty)