关于递归条件问题
来源：5-4 复杂的穿针引线 Swap Nodes in Pairs
慕仰7036876
2020-11-30
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) {
return head;
}
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
ListNode list1 = sortList(head, mid);
ListNode list2 = sortList(mid, tail);
ListNode sorted = merge(list1, list2);
return sorted;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
老师，这是leetcode的官方解，他说的中止递归条件是当链表为空或只有一个节点的时候。链表为空我理解了，但是链表只有一个节点的代码我没看懂，明明有head和tail两个节点呀，最开始tail确实是空，但是在递归过程中不是一直是空呀。这不就代表链表里有两个节点吗？怎么是只有一个节点呢，我调试了一下，确实在递归过程中是有两个节点这种情况在的，而且在调试中是处于只有一个节点时返回head那一行。我有点晕，我知道做递归只用考虑判断终止条件和递归关系式，不需要考虑中间的事，但是这种很明显在递归过程中不是一个节点的也可以不用考虑吗？明明终止条件是只有一个节点，写成代码就是两个节点了，我可以理解在最开始的时候tail作为null，当时确实只有一个节点。但是在递归工程中tail迟早会变成一个有实体的节点，这里也不用考虑吗？
1回答
-
初始调用 sortList 的时候，调的是 sortList(head, null)，所以 tail == null。head.next == tail 就是看 head.next == null。
head 和 tail 不是两个节点，head 和 tail 是指向 ListNode 的引用，如果指向的是 null，那么通过 head 或者 tail 就无法访问某个节点。
熟练的使用递归以后，可以“不考虑中间的事儿”，但这不代表你不需要理解中间发生了什么。实际上理解递归的过程具体是怎样执行的非常非常重要。我建议你使用小数据量，一个节点，两个节点，三个节点，四个节点，甚至八个节点，用单步跟踪的方式，去仔细观察递归的执行过程到底是怎样的，递归函数一层一层是如何执行的，相应的各个变量是如何变化的。如果你非常透彻的理解了递归，你才能做到“不考虑中间的事儿”，因为其实你在写递归的过程，已经知道中间发生了什么。
我在我的相对专注基础的体系课程中，特地对很多递归过程进行了细致的模拟，就是这个目的，如果有需要可以参考：https://class.imooc.com/sale/datastructure
继续加油！：）
10
相似问题