3
\$\begingroup\$

Here is my function which convert linked list in the following order:

Example:

Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3

Output: 3->2->1->6->5->4->8->7->NULL.

void SingleList::orderSort3()
{
    // If linked list is empty or there is only one node or two nodes in list
    if(getHead() == NULL || getHead()->getNext() == NULL || getHead()->getNext()->getNext() == NULL)
        return;
    // Initialize previous and current pointers
    ISingleNode *prev = getHead();
    ISingleNode *current = getHead()->getNext()->getNext();

    // Change head before proceeeding, because this head will be useful at last.
    setHead(current);

    // Traverse the list and swap
    while(true)
    {
        ISingleNode *tempNext = current->getNext();
        current->setNext(prev->getNext());
        prev->getNext()->setNext(prev);

        // check remaining node is not empty or single node.
        if(tempNext == NULL || tempNext->getNext() == NULL)
        {
            prev->setNext(tempNext);
            break;
        }
        // check remaining nodes are not only 2.
        if(tempNext->getNext()->getNext() == NULL)
        {
            prev->setNext(tempNext->getNext());
            prev = tempNext;
            current = tempNext->getNext();
        }
        else // 3 nodes are available.
        {
            prev->setNext(tempNext->getNext()->getNext());
            prev = tempNext;
            current = tempNext->getNext()->getNext();
        }

    }
}

This is my number of elements in the linked list:

8388607
14348907

Please help me to optimize this code. If you require full code then let me know and I will add more. But I guess this is the main() function, which reverses the linked list. It takes only a head pointer as an argument and it will sort without returning. This is what I want, but it takes too much time.

Does it depend on our laptop configuration and process as well?

Full source:

#pragma once

#include <cstdlib>
#include <iostream>

struct ISingleNode
{
    ISingleNode() {}
    virtual ~ISingleNode() {}
    virtual void setValue(int value) = 0;
    virtual int getValue() = 0;
    virtual ISingleNode * getNext() = 0;
    virtual void setNext(ISingleNode * next) = 0;
};

struct ISingleList
{
    ISingleList() {};
    virtual ~ISingleList() {};
    virtual ISingleNode * getHead() = 0;
    virtual void setHead(ISingleNode * head) = 0;
    virtual void addHead(int value) = 0;
    virtual void orderSort2() = 0;
    virtual void orderSort3() = 0;
};

class SingleList : public ISingleList
{
public:
    SingleList() {};
    ~SingleList() {};
    ISingleNode *getHead();
    void setHead(ISingleNode * head);
    void addHead(int value);
    void orderSort2();
    void orderSort3();
    ISingleNode* SingleList::reverse(ISingleNode *head);
private:
    ISingleNode *head_;
};

class SingleNode : public ISingleNode
{
public:
    SingleNode() : next_(NULL), value_(0) {}
    ~SingleNode() {}
    void setValue(int value);
    int getValue();
    ISingleNode * getNext();
    void setNext(ISingleNode * next);
private:
    ISingleNode* next_;
    int value_;

};

void SingleNode::setValue(int value)
{
    value_ = value;
}
int SingleNode::getValue()
{
    return value_;
}
ISingleNode * SingleNode::getNext()
{
    return next_;
}
void SingleNode::setNext(ISingleNode * next)
{
    next_ = next;
}

ISingleNode *SingleList::getHead()
{
    return head_;
}
void SingleList::setHead(ISingleNode * head)
{
    head_ = head;
}
void SingleList::addHead(int value)
{
    ISingleNode * currentNode = new SingleNode();
    currentNode->setValue(value);
    currentNode->setNext(head_);
    head_ = currentNode;
}

void SingleList::orderSort2()
{
    // If linked list is empty or there is only one node in list
    if(getHead() == NULL || getHead()->getNext() == NULL)
        return;
    // Initialize previous and current pointers
    ISingleNode *prev = getHead();
    ISingleNode *current = getHead()->getNext();
    ISingleNode *tempNext;
    // Change head before proceeeding, because this head will be useful at last.
    setHead(current);
    while(true)
    {
        tempNext = current->getNext();
        current->setNext(prev);// Change next of current as previous node
        // If next NULL or next is the last node
        if(tempNext == NULL || tempNext->getNext() == NULL)
        {
            prev->setNext(tempNext);
            break;
        }
        // Change next of previous to next next
        prev->setNext(tempNext->getNext());
        // Update previous and curr
        prev = tempNext;
        current = prev->getNext();
    }
}

void SingleList::orderSort3()
{
    // If linked list is empty or there is only one node or two nodes in list
    if(getHead() == NULL || getHead()->getNext() == NULL || getHead()->getNext()->getNext() == NULL)
        return;
    // Initialize previous and current pointers
    ISingleNode *prev = getHead();
    ISingleNode *current = getHead()->getNext()->getNext();

    // Change head before proceeeding, because this head will be useful at last.
    setHead(current);

    // Traverse the list and swap
    while(true)
    {
        ISingleNode *tempNext = current->getNext();
        current->setNext(prev->getNext());
        prev->getNext()->setNext(prev);

        if(tempNext == NULL || tempNext->getNext() == NULL)
        {
            prev->setNext(tempNext);
            break;
        }
        if(tempNext->getNext()->getNext() == NULL)
        {
            prev->setNext(tempNext->getNext());
            prev = tempNext;
            current = tempNext->getNext();
        }
        else
        {
            prev->setNext(tempNext->getNext()->getNext());
            prev = tempNext;
            current = tempNext->getNext()->getNext();
        }

    }
}

int main()
{
    SingleList single_list;

    for(int i = 8388607 - 1; i >= 0; --i)
    {
        int value = i;
        single_list.addHead(i);
    }
    single_list.orderSort3();
}
\$\endgroup\$
0
2
\$\begingroup\$
  • This is a little unclear:

    for(int i = 8388607 - 1; i >= 0; --i)
    

    Although you have stated the value of 8388607, you should preferably make it a constant in the code as well:

    const int values = 8388607;
    

    Then just put that into the loop:

    for (int i = values - 1; i >= 0; --i)
    

    This will also make it a little easier to change this value.

  • It's actually uncommon for a linked list to have getters and setters. Also, the specific node type is not supposed to be exposed to the client code, which would be the case for getters and setters. Plus, if you're just trying to reverse the linked list, then the client shouldn't need this.

    This can be changed by removing these functions (or at least making them private) and putting the ISingleNode implementation into SingleList, also as private.

  • Since you're using C++11, you should use nullptr instead of NULL.

\$\endgroup\$
2
  • \$\begingroup\$ In most languages (That I know at least), constants are CAPS_SNAKE_CASE. If that holds for C++(11) as well, values should be VALUES. \$\endgroup\$
    – Nic
    Jun 6 '15 at 21:18
  • \$\begingroup\$ @QPaysTaxes: Yes, that is a good point. But since this isn't a macro (which more commonly use all-caps), I'm hesitant to mention it here. \$\endgroup\$
    – Jamal
    Jun 6 '15 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.