This approach involves using a dummy node to ease the merging process. A dummy node is a temporary node that helps in easily managing edge cases such as initializing the result list and returning the correct head of the list. We will iterate over both lists, and in each iteration, we'll add the smallest current node to our result list. The time complexity of this method is O(n + m), where n and m are the lengths of the two lists.
Time Complexity: O(n + m), where n and m are the lengths of list1 and list2.
Space Complexity: O(1), since we are only using a constant amount of extra space.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
10 struct ListNode dummy;
11 struct ListNode* tail = &dummy;
12 dummy.next = NULL;
13
14 while (list1 && list2) {
15 if (list1->val <= list2->val) {
16 tail->next = list1;
17 list1 = list1->next;
18 } else {
19 tail->next = list2;
20 list2 = list2->next;
21 }
22 tail = tail->next;
23 }
24 tail->next = list1 ? list1 : list2;
25 return dummy.next;
26}This C program implements the iterative approach using a dummy node. We create a dummy node that acts as a starting point for our merged list. A pointer 'tail' is used to keep track of the end of the merged list. We iterate through the lists, always choosing the smaller head node and updating our tail pointer. If one list is exhausted before the other, we simply attach the remainder of the other list to the merged list. Finally, the next node of our dummy node is the head of our merged list.
The recursive approach simplifies merging by using recursive function calls to naturally handle merging nodes. This method leverages the call stack to handle the comparisons and merging order, with each function call processing pairwise comparisons when identifying the next node for the merged list. The recursion terminates when either list is fully traversed, thereby appending the remainder of the other list if needed. The recursive nature implicitly manages the combination of currently smallest nodes. The complexity is linear relative to the combined size of the lists.
Time Complexity: O(n + m), where n and m are the lengths of list1 and list2.
Space Complexity: O(n + m), due to recursive stack space required by function calls.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
10 if (!l1) return l2;
11 if (!l2) return l1;
12
13 if (l1->val <= l2->val) {
14 l1->next = mergeTwoLists(l1->next, l2);
15 return l1;
16 } else {
17 l2->next = mergeTwoLists(l1, l2->next);
18 return l2;
19 }
20}This recursive C solution merges two lists by repeatedly choosing the node with the smaller value. The function returns nodes by linking them through recursive calls that serve as connections for adjoining nodes. Upon encountering null for either input list, the method returns the other list to connect any remaining nodes. In each call, the smaller node is chosen and its 'next' linkage field is updated to sequence-based recursive evaluations of the list tails until fully sorted into the merged output.