Inverting a DoublyLinked list in C++

Question

I'm learning C++ and experimenting with it. Now, I have came to a point where I don't really like one of my solutions.

#include <iostream>

using namespace std;

//template<class T>
class List{
    public:
    struct ListElem {
            ListElem(int iElem, ListElem* iNext, ListElem* iPrev): mElem(iElem), pNext(iNext), pPrev(iPrev){
                if(pNext != nullptr){
                    pNext->pPrev = this;
                }
                if(pPrev != nullptr){
                    pPrev->pNext = this;
                }
            }

            friend ostream& operator<<(ostream& os,const ListElem& crArg) {
            os << " " << crArg.mElem;
            if (crArg.pNext)
                os << *crArg.pNext;
            return os;
        }


        public:
            int mElem;
            ListElem* pNext;
            ListElem* pPrev;
    };




    void push_front(int iElem){
        if(mHead == nullptr){
            mTail = mHead = new ListElem(iElem,mHead,nullptr);
        }else{
            mHead = new ListElem(iElem,mHead,nullptr);
        }

    }


    void push_back(int iElem){
        if(mTail == nullptr){
            mHead = mTail = new ListElem(iElem,nullptr,mTail);
        }else{
            mTail = new ListElem(iElem,nullptr,mTail);
        }

    }



    void invert(){
        for(ListElem* elem = mHead; elem != nullptr; elem = elem->pPrev){
            ListElem* tmp = elem;
            tmp = elem->pNext;
            elem->pNext = elem->pPrev;
            elem->pPrev = tmp;
        }
        ListElem* pTmpTail = mTail;
        mTail = mHead;
        mHead = pTmpTail;
    }


        friend ostream& operator<<(ostream& os,const List& crArg) {
        if (crArg.mHead)
            os << *crArg.mHead;
        return os;
    }



    private:
        ListElem* mHead = nullptr;
        ListElem* mTail = nullptr;
};




int main(){
    List l;
    l.push_back(1);
    l.push_front(10);
    l.push_back(40);
    l.push_back(30);
//  l.push_front(10);
//  l.push_front(20);
//  l.push_back(30);
    cout << l << endl;
    l.invert();
    cout << l << endl;
    return 0;
}

This is my code and I want to invert the list. My function works invert() but it's ugly and, to me, not very good. It's a task that I found and it says: I can only go 1 time through the List and don't use any other helper list or dynamic data structure. Also, it should work for even and odd elements of the list.

What do you think? is there a better way to solve this. Maybe smarter and more readable?

Answer 1

void invert(){
    ListElem* lo = mHead;
    ListElem* hi = mTail;

    while (lo != hi && //have not met
           lo->pPrev != hi) // have not crossed
    {
        std::swap(lo->mElem, hi->mElem);
        lo = lo->pNext;
        hi = hi->pPrev;
    }
}

What this does:

1. Points lo and hi at the beginning and end of the list
2. Tests that lo and hi have not yet converged.
   1. Empty list case handled lo and h are both pointing NULL and equal
   2. 1 item case handled lo and hi are both pointing to the same node and equal.
3. Swaps the data at lo and hi's nodes. It does not swap the nodes. For an int, it's much easier to swap the data than to it is to change the 4 links that must be updated. For larger data, this may not hold, but the complexity of the function goes way up. Your call as to whether or not it would be worth it.
4. Re-points lo and hi to bring them closer to convergence.
5. Go to 2.

Because the data in the list swaps its way to convergence, there are never more than length / 2 iterations.

Answer 2

The code seems fine to me, but if you want to make thing look better, you can use std::swap.

for(auto elem = mHead; elem; elem = elem->pPrev)
     std::swap(elem->pNext, elem->pPrev);
std::swap(mHead, mTail);