C++ Programming - Split Linked List into Two

Given a linked list



We have to split it into two. One of the obvious way is to traverse the linked list once get the count and terminating at the midpoint. But it will be of the order n + n/2. Another solution is to add intermediate elements into another linked list which will be of the order n.




Here is the solution (C++):



template  class node {
    T val;
    node *nxt;
public:
    node(T v): val(v), nxt(NULL) {}
    node(T v, node *n): val(v), nxt(n) {}

    T& operator()()
    {
        return val;
    }

    node *next()
    {
        return nxt;
    }

    void next(node *n)
    {
        nxt = n;
    }

    T& operator==(T v)
    {
        val = v;
    }
};

template  class Util
{
    public:
    static node *insert(node **begin, int value)
    {
        node *me = new node(value);

        if ( (me == NULL) || (begin == NULL))
            return me;

        if ( *begin == NULL )
            *begin = me;
        else
            last(*begin)->next(me);

        return me;
    }

    static bool remove(node **begin, int value)
    {
        if ( (begin == NULL) || (*begin == NULL))
            return false;

        node *me = *begin, *prev = NULL;

        while(me) {
            if ( (*me)() == value )
                break;
            prev = me;
            me = me->next();

        }

        if ( *begin == me )
            *begin = me->next();

        if ( prev && me )
            prev->next(me->next());

        delete me;

        return (me != NULL);
    }

    static node find(node *me, int value)
    {
        while(me) {
            if ( (*me)() == value )
                break;
            me = me->next();
        }
        return me;
    }

    static node *split(node *me)
    {
        if ( (me == NULL) || (me->next() == NULL))
            return NULL;

        node *nme = me->next();

        node *sec = nme;

        while(nme) {
            me->next(nme->next());

            me = nme;
            nme = nme->next();
        }

        return sec;
    }

    static void print(node *me)
    {
        while(me) {
            std::cout << (*me)();
            me = me->next();
            if ( me ) std::cout << " -> ";
        }
        std::cout << "--|" << std::endl;
    }

    static node* last(node *begin)
    {
        node *theone = NULL;
        if (begin == NULL) return theone;

        theone = begin;
        while(theone->next() != NULL)
        {
            theone = theone->next();
        }

        return theone;
     }
};

int main()
{
    node *first = NULL;
    int input[] = { 1,2,3,4,5,6,7};

    for(int i = 0 ; i < sizeof(input)/sizeof(input[0]); ++i)
        Util::insert(&first,input[i]);

    std::cout << "Input: " << std::endl;
    Util::print(first);

    node *second = Util::split(first);

    std::cout << "Output: " << std::endl;
    Util::print(first);
    Util::print(second);
}


Labels: ,

About this entry

You’re currently reading “C++ Programming - Split Linked List into Two,” an entry on ANOOB BACKER Technical Blog

Published:
11:02 am
by -