Tuesday, November 25, 2014

How to revert a singly linked list

struct Node
{
    Node* next;
    int   value;
};

Node* revert_iteratively(Node* node)
{
    Node* new_node = nullptr;

    while (node)
    {
        auto next  = node->next;
        node->next = new_node;
        new_node   = node;
        node       = next;
    }

    return new_node;
}

Node* revert_iteratively_simple(Node* node)
{
    using std::swap;

    for (Node* tmp = nullptr; swap(node, tmp), tmp; swap(node, tmp->next));

    return node;
}

Node* revert_recursively(Node* node)
{
    if (!node || !node->next)
        return node;

    auto new_node = revert_recursively(node->next);
    node->next->next = node;
    node->next = nullptr;

    return new_node;
}

No comments:

Post a Comment