Cracking The Coding Interview/Q 2.4

From Software Engineers Wiki
Jump to: navigation, search

Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

Answer #1

Traverse from front looking for a node with value greater than the partition value. Traverse from end looking for a node with value smaller than the partition value. Swap these two nodes. Repeat this until it meet in the middle.

void partition_list(std::list<int> &rlist, int value)
{
        std::list<int>::iterator ir_front, ir_end;

        /* if the list is empty, do nothing */
        if (rlist.empty())
                return;

        /* find first and list item */
        ir_front = rlist.begin();
        ir_end = rlist.end();
        --ir_end;

        /* swap values if necessary */
        for (;;) {
                /* find a node with value over partition value from front */
                for (;;) {
                        if (ir_front == ir_end)
                                return;
                        if (*ir_front > value)
                                break;
                        ++ir_front;
                }
                /* find a node with value under partition value from back */
                for (;;) {
                        if (ir_front == ir_end)
                                return;
                        if (*ir_end < value)
                                break;
                        --ir_end;
                }
                /* swap */
                int tmp = *ir_front;
                *ir_front = *ir_end;
                *ir_end = tmp;
        }
}

Test program:

void print_list(std::list<int> &rlist)
{
        std::list<int>::iterator ir;

        for (ir = rlist.begin(); ir != rlist.end(); ++ir)
                std::cout << *ir << " ";

        std::cout << std::endl;
}

class partition_list_test_10 {
private:
        std::list<int> m_list;
public:
        partition_list_test_10(std::initializer_list<int> il) : m_list { il } {
                std::cout << "Testing\n";
                print_list(m_list);
                partition_list(m_list, 10);
                print_list(m_list);
        }
};

int main(void)
{
        partition_list_test_10 l1 { };
        partition_list_test_10 l2 { 9 };
        partition_list_test_10 l3 { 11, 9 };
        partition_list_test_10 l4 { 9, 10, 11 };
        partition_list_test_10 l5 { 13, 14, 17, 1, 2, 3 };
        partition_list_test_10 l6 { 13, 14, 17, 6, 1, 2, 3 };
        partition_list_test_10 l7 { 13, 14, 17, 6, 1, 2, 3, 8, 4, 0 };

        return 0;
}

Test result:

Testing


Testing
9 
9 
Testing
11 9 
9 11 
Testing
9 10 11 
9 10 11 
Testing
13 14 17 1 2 3 
3 2 1 17 14 13 
Testing
13 14 17 6 1 2 3 
3 2 1 6 17 14 13 
Testing
13 14 17 6 1 2 3 8 4 0 
0 4 8 6 1 2 3 17 14 13 

Answer #2

Another way is to build two separate linked lists, one with nodes with value lower than the partition value, and another list with other nodes. Then merge the lists together. This can be done with custom designed linked list.

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox