How to swap the first and last elements of a linked list

I am trying to swap the first and last elements of a linked list, but I have not been able to find a solution. My logic, or pseudo code, is to:

  • set the second-to-last node’s next to the first node.
  • set the first node’s next to a nullptr.
  • set the last node’s next to the first node.

My current code is:

void SingleList::swapFirstAndLast()
{
    Node *current = first;

    while (current->getNext()->getNext() != nullptr)
    {
        current = current->getNext();
    }
    // current is equal to the second to last node

    //set last node to first node
    current->getNext()->setNext(first);
    //set first node to nullptr
    first->setNext(nullptr);
    //set second to last to first node
    current->setNext(first);
    // set the first equal to the last node
    first = current->getNext();
}

And my current output is:

Swap first and last nodes: 
List before :    200 50 300 25 


 --------------------------- 
List after :    200 

I’m not necessarily looking for a direct code answer, but any tips or advice on what I am missing here would be much appreciated.

Answer

Your logic has a flaw in its third point.

  • set the last node next to the first node

It should be.

  • set the old last node as the new first node.

Lets walk through your pseudo code. I assume first is a global pointer that points to the first node of your list.

|200|50|300|25|
 ^
first

after the while run the current pointer now points to the node with a value of 300

|200|50|300|25|
 ^      ^
 first  current 

then we change the node with value 25 to point to first which leads to this

|50|300|25|200|
    ^      ^
   current first 

after that we close the list at first by pointing it to null, And set first as next of current

|50|300|200|
    ^   ^
current first 

Now the error can be seen the reference to 25 is now lost. After that we change the global first pointer to point to the next node of current which should be the node with value 25 but is not since it was replaced with the original first node.

To fix this you should change the end of your function like this.

Node * oldLast = current->getNext();
//set second to last to first node
current->setNext(first);
// set the first equal to the last node
first = oldLast;

Leave a Reply

Your email address will not be published. Required fields are marked *