LeetCode Hot100 第 21 题:合并两个有序链表(C 语言版)
递归解题思路递归方法的核心思想是将问题分解为更小的子问题。对于合并两个有序链表可以比较两个链表的头节点将较小的节点作为合并后的链表的头节点然后递归地合并剩余部分。算法步骤比较两个链表的头节点值选择较小的节点作为合并后的链表的头节点。将较小节点的next指针指向递归合并后的剩余链表。递归终止条件是其中一个链表为空直接返回另一个链表。代码实现struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { // 递归出口其中一条链表为空直接返回另一条 if(list1 NULL) return list2; if(list2 NULL) return list1; //解决节点为NILL的情况 // 当前list1更小选list1作为当前节点 if(list1-val list2-val) //list1-val这个指针指向的节点里面的 val 数值。 { // list1后面拼接list1-next 和 list2 合并后的链表 list1-next mergeTwoLists(list1-next, list2); return list1; } else { // list2更小或相等选list2作为当前节点 list2-next mergeTwoLists(list1, list2-next); return list2; } }时间复杂度分析递归方法的时间复杂度是O(n m)其中n和m分别是两个链表的长度。每次递归调用都会处理一个节点直到其中一个链表为空。空间复杂度分析递归方法的空间复杂度是O(n m)因为递归调用的栈空间取决于链表的长度。在最坏情况下递归深度等于两个链表的长度之和。注意事项递归方法虽然简洁但在处理极长的链表时可能会导致栈溢出。对于大规模数据迭代方法更为安全。