Нуждаете се от помощ относно псевдокод/алгоритъм - обединяване на свързани списъци

Първо има директива за препроцесор:

#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, условието се оценява като false и цикълът 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.

След това цикълът преминава към следващата си итерация с този нов списък1.

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

Дано това има смисъл! Това е доста изящно решение и би било много по-лесно да се нарисува, отколкото да се обясни с думи.