Link 按特定顺序列出 C++

Question

我必须按照低 -> 高 -> 低 -> 高 -> 低的模式订购给定的 link 列表 1 -> 2 -> 3 -> 4 -> 5 导致 1 - > 3 -> 2 -> 5 -> 4.

我已经编码了：

#include <iostream>

using namespace std;

struct node
{
    int data;
    node *next;
};

class linked_list
{
private:
    node *head,*tail;
public:
    linked_list()
    {
        head = NULL;
        tail = NULL;
    }

    void add_node(int n)
    {
        node *tmp = new node;
        tmp->data = n;
        tmp->next = NULL;

        if(head == NULL)
        {
            head = tmp;
            tail = tmp;
        }
        else
        {
            tail->next = tmp;
            tail = tail->next;
        }
    }

    node* getHead()
    {
        return head;
    }
};

int main()
{
    linked_list a;
    a.add_node(1);
    a.add_node(2);
    a.add_node(3);
    a.add_node(4);
    a.add_node(5);
    bool leave= false;
    int direction = 1;
    node* considered_node = new node(*(a.getHead()));
    while(true)
    {
        if (considered_node->next == NULL)
        {
            break;
        }
        else if (direction*considered_node->next->data < direction*considered_node->data)
        {
            int t= direction*considered_node->next->data;
            int p = direction*considered_node->data;
            int tmp = considered_node->next->data;
            considered_node->next->data = considered_node->data;
            considered_node->data = tmp;
        }
        delete considered_node;
        considered_node = considered_node->next;
        direction = -1*direction;
    }
    return 0;
}

但是我在遍历 link 列表并删除指针以避免内存泄漏的方式上犯了一个错误。我不想只更改 for 循环的 link 列表的声明。

Answer 1

在这里，我试着解释一下。看，https://ideone.com/PdBY6W。

int direction = 1;

node* considered_node = new node(*(a.getHead()));
while(true)
{
    if (considered_node->next == NULL)
    {
        break;
    }

    // do not need else here
    if (direction*considered_node->next->data < direction*considered_node->data)
    {
        // do not need t and p
        // int t= direction*considered_node->next->data;
        // int p = direction*considered_node->data;
        int tmp = considered_node->next->data;
        considered_node->next->data = considered_node->data;
        considered_node->data = tmp;
    }

    // if you delete considered_node, then you can not access it's address
    // after deleting it. So comment the deletion
    // delete considered_node;
    considered_node = considered_node->next;
    direction = -1*direction;
}

// Notice after finishing the for loop, considered_node is now at the tail
// node of the list. So, before deleting considered_node move it's reference
// to the next node and then delete. Otherwise, if you delete without moving
// the reference, the deletion will delete the tail node, in which case the 
// list will be 1-> 3 -> 2 -> 5 -> 0.
considered_node = considered_node->next;
delete considered_node;

// now the list is 1-> 3 -> 2 -> 5 -> 4

Answer 2

如果我理解正确，那么当第一个节点必须不大于第二个节点并且第二个节点必须不小于第三个节点时，您需要重新排序列表，依此类推。

如果是这样，则无需使用 operator new 对列表重新排序。

这是一个演示程序。我对列表定义做了一些小改动。例如，结构节点应该对列表的用户隐藏。它应该被定义为列表定义中的私有数据成员。

#include <iostream>
#include <utility>

class linked_list
{
private:
    struct node
    {
        int data;
        node *next;
    } *head = nullptr, *tail = nullptr;

public:
    linked_list() = default;

    void add_node( int data )
    {
        node *tmp = new node { data, nullptr };

        if ( head == NULL )
        {
            head = tail = tmp;
        }
        else
        {
            tail = tail->next = tmp;
        }
    }

    void reorder()
    {
        int direction = 0;

        auto condition = [&direction]( const auto &a, const auto &b )
        {
            return ( direction ^= 1 ) ?  b < a : a < b;
        };

        node **current = &head;

        for ( ; *current && ( *current )->next; current = &( *current )->next )
        {
            if ( condition( ( *current )->data, ( *current )->next->data ) )
            {   
                node * &next = ( *current )->next;
                std::swap( *current, next );
                std::swap( ( *current )->next, next->next );
            }
        }

        tail = *current;
    }

    friend  std::ostream & operator <<(std::ostream &os, const  linked_list &list)
    {
        for ( const node *current = list.head; current != nullptr; current = current->next)
        {
            os << current->data << " -> ";
        }

        return os << "null";
    }   
};

int main() 
{
    linked_list list;
    int a[] = { 1, 2, 3, 4, 5 };

    for ( int data : a ) list.add_node( data );

    std::cout << list << '\n';

    list.reorder();

    std::cout << list << '\n';

    int b[] = { 6, 7, 8, 9, 10 };

    for ( int data : b ) list.add_node( data );

    std::cout << list << '\n';

    list.reorder();

    std::cout << list << '\n';

    return 0;
}

它的输出是

1 -> 2 -> 3 -> 4 -> 5 -> null
1 -> 3 -> 2 -> 5 -> 4 -> null
1 -> 3 -> 2 -> 5 -> 4 -> 6 -> 7 -> 8 -> 9 -> 10 -> null
1 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6 -> 9 -> 8 -> 10 -> null

注意，对列表重新排序后，需要调整列表的指针尾部。否则向列表添加新元素可能无效。

Link 按特定顺序列出 C++

Link List C++ in certain order

c++

swap

class

linked-list

singly-linked-list