Анализ кода для слияния двух связанных списков в отсортированном порядке - PullRequest
Новая
       6

Анализ кода для слияния двух связанных списков в отсортированном порядке

0 голосов
/ 28 февраля 2019

Ребята. Меня пытались объединить два отсортированных Одиночных Связанных Списка в отсортированном порядке.В SO я нашел рекурсивный подход для этого.Я очень старался понять код, но не смог полностью понять!Есть ли кто-нибудь, кто может помочь мне понять это ясно.Заранее спасибо!

Вот фрагменты кода: 

Node MergeLists(Node list1, Node list2) {
 if (list1 == null) return list2;
 if (list2 == null) return list1;

 if (list1.data < list2.data) {
   list1.next = MergeLists(list1.next, list2);
   return list1;
 } else {
   list2.next = MergeLists(list2.next, list1);
   return list2;
 } 
}

Ссылка: Интервью: Объединение двух отсортированных односвязных списков

К сожалению, длятратить ваше время!:(

Ответы [ 2 ]

0 голосов
/ 05 марта 2019 
1. Node MergeLists(Node list1, Node list2) {
2.   if (list1 == null) return list2;
3.   if (list2 == null) return list1;

4.   if (list1.data < list2.data) {
5.     list1.next = MergeLists(list1.next, list2);
6.     return list1;
7.   } else {
8.     list2.next = MergeLists(list2.next, list1);
9.     return list2;
10.  } 
11. }

Изначально каждый из двух связанных списков (LL1 и LL2) будет отсортирован (индивидуально).Код только объединяет их.Иллюстрирование на примере SIMPLE

например.ЛЛ1;1->3->4

LL2: 6->8->9

, поскольку list1.data < list2.data (строка 4) всегда будет истинным (до базового условия выхода (строка 2)), LL1 будет повторяться доконец.И наконец, next последнего элемента (LL1) будет указывать на первый элемент LL2 (строка 5).Таким образом, 2 LL будут объединены, и мы получим 1->3->4->6->8->9

Конечно, с более сложным примером будет больше рекурсий.

0 голосов
/ 28 февраля 2019

Вот что я могу добавить к коду: 

Node MergeLists(Node list1, Node list2) {
 if (list1 == null) return list2;      //Exit strategy
 if (list2 == null) return list1;      //Exit strategy

 if (list1.data < list2.data) {      //If current item in list1 is less than current 
                                     //item in list2 we put the item of list1 in our
                                     //sorted list and continue the algorithm recursivly
                                     //and add the node from recursive function to list1.next
   list1.next = MergeLists(list1.next, list2);
   return list1;
 } else {                            //exactly like above but this time we continue with list2
   list2.next = MergeLists(list2.next, list1);
   return list2;
 } 
}
...