Яндекс

Напишите структуру односвязного списка с данными.

struct list
{
    struct list* next;
    int my;
};

• #linked-list
• #data-structures

Первое задание в общем вебовском редакторе, без компилятора.

Напишите функцию, которая на вход принимает два односвязных списка, а на выходе возвращает один список, отсортированный по данным из первых двух, без всякого копирования (in-place слияние).

list* joint(list* a, list* b)
{
    list fst = { a }; list scd = { b }; list trd = {0};
    list* res = &trd;
    while (fst.next || scd.next) {
        int ref = 0;
        list* dst = 0;
        bool flg = 0;
        for (list* src = fst.next? &fst:&scd; src->next; src = src->next->next || flg? src->next : (flg = 1, &scd) ) {
            if (src->next->my > ref) {
                ref = src->next->my;
                dst = src;
            }
        }
        res->next =  dst->next; 
        dst->next = res->next->next;
        res = res->next; 
    }
    return trd.next;
}

• #linked-list
• #sorting
• #merge
• #in-place
• #algorithms

Кандидат пытался уместить решение в два цикла из соображений сложности; интервьюер сказал, что не видит осмысленности в черновом коде, и предложил завершить собеседование.