按排序顺序合并两个链表的代码分析

Question

伙计们，我试图以排序顺序合并两个排序的单链接列表。在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;
 } 
}

链接：访谈：合并两个排序的单链表

对不起，浪费你的时间！：（

Answer 1

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<代码>1-

LL2:6-

因为list1。数据

当然，对于更复杂的示例，将有更多的递归。

Answer 2

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

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