Нужна помощь по псевдокоду/алгоритму - слияние связанных списков

Сначала есть директива препроцессора:

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Это означает, что когда препроцессор подготавливает единицу трансляции к компиляции, всякий раз, когда он встречает SWAP_PTRS(a, b), он заменяет ее на

do { void *t = (a); (a) = (b); (b) = t; } while (0)

Давайте распакуем это. Это просто функция для замены одной пары указателей a и b.

Поскольку цикл представляет собой цикл do ... while, он будет выполняться перед проверкой условия цикла. Внутри цикла объявляется новый указатель void t. Это совместимо с любым типом указателя, поэтому независимо от типа указателя a и b они совместимы с t.

Тогда это стандартный обмен:

1. Назначьте a t
2. Назначить b a
3. Назначьте t b

После подкачки проверяется состояние цикла. Поскольку это 0, условие оценивается как ложное, и цикл do ... while завершается. Другими словами, он будет выполнен один и только один раз, что и требуется, поскольку цель состоит в том, чтобы просто поменять местами одну пару указателей.

Вот псевдокод настоящей функции MergeLists.

Algorithm MergeLists
Receives: pointer to head node of linked list list1
    pointer to head node of linked list list2
Returns: pointer to head node of merged list

1. Declare pointer list for merged list and initialize to NULL
2. Declare pointer to pointer pNext and initialize it to the address of the merged list
3. if (list2 is NULL)  // empty list
    3.1 return list1   // nothing to merge
4. loop while list1 is not NULL
    4.1 if (data in list1 is greater than data in list2)
        4.1.1 swap list1 and list2
    4.2 set dereferenced value of pNext to list1
    4.3 set pNext to the address of the next node in list1
    4.4 set list1 to the dereferenced value of pNext // same as list1 = list1->next
5. end loop for list1
6. set the dereferenced value of pNext to list2
7. return list

Это довольно сложная логика. Вся тяжелая работа находится в цикле while. Вот разбивка:

Есть два указателя на узлы связанного списка, list1 и list2. Первый шаг в цикле while устанавливает узел с меньшим значением данных как list1, а другой — как list2. При необходимости это устанавливается с помощью макроса SWAP_PTRS.

В начале *pNext указывает на этот list1 с меньшим значением данных. В самый первый раз в цикле, поскольку *pNext также является list (объединенный список), list теперь также будет указывать на то же место.

Следующий шаг сбрасывает pNext на адрес следующего узла в list1. Однако это не изменит того, куда указывает list (pNext — двухуровневый указатель, и на этом шаге мы меняем, куда указывает pNext, т. е. не туда, куда указывает *pNext).

Тогда list1 устанавливается на *pNext, т.е. на list1->next.

Затем цикл переходит к следующей итерации с этим новым list1.

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

Надеюсь, это имеет смысл! Это довольно изящное решение, и, честно говоря, его было бы намного легче нарисовать, чем объяснить словами.