分析代码以分类顺序合并两个链接列表

Question

我试图按顺序合并两个排序的单个链接列表。在这中，我找到了一种递归方法来做到这一点。我很难理解代码，但无法完全理解！那里的任何人都可以帮助我清楚地弄清楚这一点。预先感谢！

这是代码段：

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;
 } 
}

链接：访谈：合并两个分类的单链接列表

对不起，浪费了您的时间！:(

Answer 1

这是我可以添加到代码的内容：

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;
 } 
}

Answer 2

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）中的每个列表（LL1和LL2）进行分类。代码仅合并它们。用简单示例

说明

例如。ll1; 1->3->4

ll2： 6->8->9

由于 list1.data < list2.data（第4行）将始终为真（直到基本出口条件（第2行）），LL1将被恢复到结束。最后，（LL1的最后一个元素）的next将指向LL2的第一个元素（第5行）。这样，将合并2个LLS，我们将获得1->3->4->6->8->9

当然，有了一个更复杂的示例，会有更多的递归。