如何对双向链表的节点而非节点值进行排序（附问题代码）

我正在完成一项作业，要求对双向链表的**节点（而非节点值）**进行排序。原本计划构建新的有序链表后重置头尾，但当前实现的sort函数陷入循环，求解决思路。

SortNode.h代码 #

#ifndef SN_H
#define SN_H

#include <string>
#include <sstream>

//SortNode class implementation here
template <class T>
class SortNode
{
    protected:
        T value;
    public:
        SortNode<T> * next;
        SortNode<T> * prev;
        SortNode(T);
        std :: string print();
        T getValue();
};

#include "SortNode.cpp"

#endif

SortList.h代码 #

#ifndef DLL_H
#define DLL_H

#include "SortNode.h"

template <class T>
class SortList 
{
    private:
        bool ascending;
        SortNode<T> * head;
        SortNode<T> * tail;

    public:
        SortList(bool);
        void add(SortNode<T>* a) ;
        SortNode<T>* remove(T val);  
        void setAsc(bool a);
        void sort() ;
        string print() ;
        SortNode<T>*getHead() ;
        string debug() ;

};


#include "SortList.cpp"

#endif

存在问题的sort函数代码 #

template <class T>
void SortList<T> :: sort()
{

cout<<"above if "<<endl;
    if (ascending == true)
    {
        SortNode<T> * node = head, *ptr = NULL ,*sortedh = NULL, *sortedt = NULL, *newnode = NULL;
        
        while (node != NULL)
        {
            newnode = node;
           
            if (!sortedh)
            {
                sortedh = node;
                sortedt = node;
            }
            else
            {
               
                ptr = head;

                while (ptr!= NULL && ptr -> getValue() < newnode -> getValue())
                {
                    ptr = ptr -> next;
                }

                if (!ptr)
                {
                    sortedt -> next = newnode;
                    newnode ->prev = sortedt;
                    sortedt = newnode;

                }
                else
                {
                    if (ptr ->prev == NULL)
                    {
                        newnode -> next = ptr;
                        ptr -> prev =newnode;
                        sortedh = newnode;
                    }
                    else
                    {
                        ptr -> prev -> next = newnode;
                        newnode -> prev =ptr -> prev;
                        newnode -> next =ptr;
                        ptr -> prev = newnode;
                    }
                    
                }


            }
            
            
            node = node -> next;
        }

      
    }
  
    
}

问题分析与修复要点 #

• 循环根源：插入新节点时未断开原链表的节点关联，且遍历指针ptr错误从原链表head开始，而非已排序的sortedh，导致节点被重复插入形成循环引用。
• 关键修复步骤：
  1. 处理当前节点前，先保存node->next，避免原链表节点丢失；
  2. 将当前节点的prev和next置空，断开原链表的残留引用；
  3. 把ptr的起始点改为sortedh，在已排序链表中寻找插入位置；
  4. 排序完成后，将原链表的head和tail更新为sortedh和sortedt。

修复后的sort函数示例 #

#include <iostream>
using namespace std;

template <class T>
void SortList<T>::sort()
{
    cout << "above if " << endl;
    if (ascending == true)
    {
        SortNode<T> *node = head, *ptr = NULL, *sortedh = NULL, *sortedt = NULL, *nextNode = NULL;
        
        while (node != NULL)
        {
            nextNode = node->next; // 保存下一个节点，避免遍历丢失
            node->prev = nullptr;  // 断开原节点前驱关联
            node->next = nullptr;  // 断开原节点后继关联

            if (!sortedh)
            {
                sortedh = node;
                sortedt = node;
            }
            else
            {
                ptr = sortedh; // 从已排序链表头部开始找插入位置
                while (ptr != NULL && ptr->getValue() < node->getValue())
                {
                    ptr = ptr->next;
                }

                if (!ptr)
                {
                    // 插入到已排序链表尾部
                    sortedt->next = node;
                    node->prev = sortedt;
                    sortedt = node;
                }
                else
                {
                    if (ptr->prev == NULL)
                    {
                        // 插入到已排序链表头部
                        node->next = ptr;
                        ptr->prev = node;
                        sortedh = node;
                    }
                    else
                    {
                        // 插入到中间位置
                        ptr->prev->next = node;
                        node->prev = ptr->prev;
                        node->next = ptr;
                        ptr->prev = node;
                    }
                }
            }
            
            node = nextNode; // 遍历原链表下一个节点
        }

        // 更新原链表头尾为已排序链表的头尾
        head = sortedh;
        tail = sortedt;
    }
}

内容的提问来源于stack exchange，提问作者DVW