public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } 请举例解释这段代码
时间: 2024-02-14 11:31:06 浏览: 33
这段代码是一个递归算法,用于合并两个有序链表。它的输入是两个链表l1和l2,返回一个合并后的有序链表。
代码的逻辑如下:
1. 首先判断特殊情况,如果l1为空,则直接返回l2;如果l2为空,则直接返回l1。
2. 如果l1的值小于l2的值,则将l1作为合并后链表的头节点,将l1的下一个节点与l2合并,即调用递归函数mergeTwoLists(l1.next, l2),并将结果赋给l1的next指针。
3. 如果l2的值小于等于l1的值,则将l2作为合并后链表的头节点,将l2的下一个节点与l1合并,即调用递归函数mergeTwoLists(l1, l2.next),并将结果赋给l2的next指针。
4. 返回合并后的链表头节点。
下面举个例子来解释这段代码的执行过程:
假设有两个有序链表l1和l2:
l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
调用mergeTwoLists(l1, l2)后,进入第一次递归:
l1.val = 1, l2.val = 2,因此选择l1作为头节点,将l1.next与l2合并:
mergeTwoLists(l1.next, l2)
进入第二次递归:
l1.val = 3, l2.val = 2,因此选择l2作为头节点,将l2.next与l1合并:
mergeTwoLists(l1, l2.next)
进入第三次递归:
l1.val = 3, l2.val = 4,因此选择l1作为头节点,将l1.next与l2合并:
mergeTwoLists(l1.next, l2)
进入第四次递归:
l1.val = 5, l2.val = 4,因此选择l2作为头节点,将l2.next与l1合并:
mergeTwoLists(l1, l2.next)
进入第五次递归:
l1为空,返回l2
返回结果:4 -> 5
返回结果:3 -> 4 -> 5
返回结果:2 -> 3 -> 4 -> 5
返回结果:1 -> 2 -> 3 -> 4 -> 5
最终返回的链表为:1 -> 2 -> 3 -> 4 -> 5。
这段代码利用了递归的思想,通过比较链表节点的值,并逐步合并两个链表中的节点,最终得到一个有序的链表。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)