Объединение двух отсортированных связанных списков
Это также покажет вам, сколько дубликатов имеет и будет заказывать результаты без объединений
SELECT `Language` , id, COUNT( id ) AS how_many
FROM `languages`
GROUP BY `Language`
HAVING how_many >=2
ORDER BY how_many DESC
5 ответов
Ваш код перегружен if -s, вставленными для обработки «особых» случаев, что сильно раздувает его и затрудняет чтение. Обычно это происходит, когда вы решаете обрабатывать особые случаи «по коду» вместо того, чтобы искать способ обрабатывать их «по данным». В заявлении, приписываемом Дэвиду Уиллеру, говорится: «Все проблемы в информатике могут быть решены с помощью другого уровня косвенного обращения». Этот «дополнительный уровень косвенного обращения» обычно очень хорошо работает со списками, помогая значительно уменьшить беспорядок, создаваемый этими if s.
Чтобы проиллюстрировать вышесказанное, вот как будет выглядеть мой код
#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)
Node* MergeLists(Node* list1, Node* list2)
{
Node *list = NULL, **pnext = &list;
if (list2 == NULL)
return list1;
while (list1 != NULL)
{
if (list1->data > list2->data)
SWAP_PTRS(list1, list2);
*pnext = list1;
pnext = &list1->next;
list1 = *pnext;
}
*pnext = list2;
return list;
}
Некоторые могут возразить, что использование дополнительного уровня косвенности в указателе pnext на самом деле затрудняет чтение кода. Я согласен, что для новичка такой подход может вызвать некоторые трудности, но для опытного программиста он должен быть легко усваиваемым как идиома.
Мое мнение, с тестовым примером
Пока все ответы были интересными и хорошо сделаны. Возможно, это больше похоже на то, что хотел бы видеть интервьюер, с DRY / DIE и TDD. : -)
#include <stdio.h>
typedef struct ns {
int data;
struct ns *next;
} Node;
Node l1[] = {
{ 1, &l1[1] },
{ 3, &l1[2] },
{ 5, &l1[3] },
{ 7, &l1[4] },
{ 9, &l1[5] },
{11, 0 },
};
Node l2[] = {
{ 2, &l2[1] },
{ 4, &l2[2] },
{ 6, 0 },
};
Node* MergeLists(Node* list1, Node* list2) {
Node *t, **xt;
for(xt = &t; list1 || list2;) {
Node **z = list1 == NULL ? &list2 :
list2 == NULL ? &list1 :
list1->data < list2->data ? &list1 : &list2;
*xt = *z;
xt = &(*z)->next;
*z = *xt;
}
*xt = NULL;
return t;
}
int main(void) {
for(Node *t = MergeLists(l1, l2); t; t = t->next)
printf("%d\n", t->data);
return 0;
}
Самая явная ошибка в вашем цикле: вы продолжаете перезаписывать mergedList-> next, теряя ранее добавленный узел. То есть, ваш возвращенный список никогда не будет содержать более двух узлов, независимо от ввода ...
Я давно не писал C, но я бы сделал это следующим образом:
Node* merge(Node* list1, Node* list2) {
Node* merged = null;
Node** tail = &merged;
while (list1 && list2) {
if (list1->data < list2->data) {
*tail = list1;
list1 = list1->next;
} else {
*tail = list2;
list2 = list2->next;
}
tail = &((*tail)->next);
}
*tail = list1 ? list1 : list2;
return merged;
}
Нет ничего более элегантного, чем это:
Node* merge2(Node* n1, Node* n2) {
n1->next = merge(n1->next, n2);
return n1;
}
Node* merge(Node* n1, Node* n2) {
return (n1 == null) ? n2 :
(n2 == null) ? n1 :
(n1->data < n2->data) ?
merge2(n1, n2) :
merge2(n2, n1);
}
Предполагая, что вы понимаете рекурсию, это предельно ясно.
Я должен отметить, что это подходит только для ответа на собеседовании (где предположительно демонстрация ясности мысли имеет большее влияние, чем просто демонстрация того, что вы умеете писать программы). На практике вы не захотите выполнять слияние таким способом, поскольку он использует глубину стека O (n) , что, вероятно, вызовет переполнение стека. Кроме того, это не хвостовая рекурсия, поэтому она не оптимизируется компилятором.