My teacher left this task:
Reverse the order of the elements of a linked list, only by manipulating pointers in each node. It is not allowed to move the item as such, nor is to create a new node for this operation.
I've tried to think in a solution for this but everytime I end up needing to create a new node pointer or calling another method that returns a created one.
Here's some code, the list is singly linked, "first" is the head of the list and "last" is the last pointer of the list.
My method for getting a node pointer:
template <class T>
Node<T>* LinkedList<T>::getNode(unsigned int i)
{
int index = 0;
if (i == 0)
return first;
Node<T>* cursor = first;
while (index != i && cursor)
{
cursor = cursor->getNext();
++index;
}
return cursor;
}
And, here's my method for reverse the list:
template <class T>
void LinkedList<T>::reverse()
{
int i = 1, j = 2;
while(j <= size)
{
getNode(size - 1)->setNext(getNode(size - j++));
if (j == size + 1)
first = getNode(size - (j - 2));
else
getNode(size - j)->setNext(getNode(size - i++));
getNode(size - 1)->setNext(nullptr);
}
last = getNode(size - 1);
}
As I said before, I needed to know if there's a way for me to do the same without using that get method (which creates a node pointer). I think that when he refers to create a new node he's talking about a node pointer because you can't create a node (an object not a pointer) and assign to it a pointer of the list.
IF there's a way I'd be really gratefull if someone shares it, and if there's no way then I'll do it the normal way. Thanks to the people who has answered.
IMO, the easiest method is to create a new head pointer, then take the elements of the existing list and push them to the top of the new list.
+---+ +---+ +---+
Head --> | A | --> | B | --> | C |
+---+ +---+ +---+
Move First Node to new List:
+---+
New List --> | A |
+---+
+---+ +---+
Head --> | B | --> | C |
+---+ +---+
Push the next node onto the new list.
+---+ +---+
New List --> | B | --> | A |
+---+ +---+
+---+
Head --> | C |
+---+
Repeat until all nodes from original list are pushed to the new list:
+---+ +---+ +---+
New List --> | C | --> | B | --> | A |
+---+ +---+ +---+
The actual coding is left as an exercise for the OP.
Note: Only pointers in the node have changed. Actual node data has not been altered, or moved.
With a doubly linked list, you need to swap the next pointer with the "previous" pointer.
+-----+ +-----+ +-----+
Head --> | A | | B | | C |
+-----+ +-----+ +-----+
(Previous) | / | | <-- | + <-- |
+-----+ +-----+ +-----+
(Next) | --> | | --> | | / |
+-----+ +-----+ +-----+
After swapping:
+-----+ +-----+ +-----+
| A | | B | | C | <-- Head
+-----+ +-----+ +-----+
(Previous) | --> | | --> | | / |
+-----+ +-----+ +-----+
(Next) | / | | <-- | + <-- |
+-----+ +-----+ +-----+
struct Node
{
int data;
Node * p_next;
};
void Reverse_List(Node * & p_list)
{
Node * p_new_list = NULL;
while (p_list != NULL)
{
// Disconnect node from original list.
Node * p_node = p_list;
p_list = p_node->p_next;
p_node->p_next = NULL;
// Push node to new list
p_node->p_next = p_new_list;
p_new_list = p_node;
}
// Set passed pointer to new list
p_list = p_new_list;
}
Making the code generic is left as an exercise to for the OP.