c++ - 在 C++ 中反转双向链表

Question

我正在学习 C++ 并尝试使用它。现在，我已经到了我不太喜欢我的解决方案之一的地步。

#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;
}

这是我的代码，我想反转列表。 我的函数有效 invert() 但它很难看，而且对我来说不是很好。这是我找到的一项任务，上面写着:我只能遍历 List 一次，并且不使用任何其他助手列表或动态数据结构。此外，它应该适用于列表的偶数和奇数元素。

你怎么看？有没有更好的方法来解决这个问题。也许更智能、更易读？

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;
    }
}

这是做什么的:

1. 在列表的开头和结尾指向lo和hi
2. 测试 lo 和 hi 还没有收敛。
   1. 处理空列表情况 lo 和 h 都指向 NULL 且相等
   2. 1 item case handled lo 和 hi 都指向同一个节点并且相等。
3. 交换lo 和hi 节点的数据。它不交换节点。对于 int，交换数据比更改必须更新的 4 个链接要容易得多。对于更大的数据，这可能不成立，但函数的复杂性会上升。您来电决定是否值得。
4. 重新指向 lo 和 hi 使它们更接近收敛。
5. 转到 2。

因为列表中的数据交换其收敛方式，所以永远不会超过 length/2 次迭代。