链表拆分为奇偶时如何"delete"原始链表？

Question

这是我使用的原始代码：

void split(Node*& in, Node*& odds, Node*& evens)
{
    /* Add code here */
    if (!in) 
    {
        odds = NULL;
        evens = NULL;
        return;
    } 
    else if (in->value % 2 == 1) 
    {
        odds = in;
        return split(in->next, odds->next, evens);
    } 
    else 
    {       
        evens = in;
        return split(in->next, odds, evens->next);
    }
}

我需要删除原来的链表，同时将值转移到新的链表中。根据问题，我必须像以前一样使用递归。如果我现在打印它，那么它会选择第一个节点并打印与该节点关联的链表。例如，对于下面给出的测试代码，我得到

18 3 5 6 8 9
18 6 8
3 5 9
18 6 8

作为输出，而我需要这个：

18 3 5 6 8 9

3 5 9
18 6 8

这里是测试代码：

void printList(Node* n) 
{ 
    while (n != NULL) { 
        cout << n->value << " "; 
        n = n->next; 
    } 
        cout << "\n";
} 

int main()
{
    Node* odds = NULL;
    Node* evens = NULL;
    Node* in = new Node{ 18, new Node{3, new Node{5, new Node{6, new Node{8, new Node{9, NULL} } } } } };
    printList(in);
    split(in, odds, evens);
    printList(in);
    printList(odds);
    printList(evens);
    return 0;
}

Answer 1

您可以移动节点到一个或另一个列表，方法是擦除原始列表中的指针：不是一个完美但有效的解决方案（如果您想要运行在编译器中查看它是如何工作的，则添加打印以供说明）

void split(Node*& in, Node*& odds, Node*& evens)
{
    Node* temp = in;
    if(!in) { 
           //std::cout << "\n"; 
           return;
    }
    in = nullptr;
    if(temp->value % 2 == 1) {
        //std::cout << "odd ";
        odds = temp;    
        return split( temp->next, odds->next, evens);
    } else {
        //std::cout << "even ";
        evens = temp;    
        return split( temp->next, odds, evens->next);
    }
}

通过使用静态（不是“堆栈”）时间，它的足迹可能不会增长：

static Node* temp;
temp = in;

链表拆分为奇偶时如何"delete"原始链表？

How to "delete" original linked list when splitting the linked list into odd and even?

c++

recursion

linked-list

singly-linked-list