合并两个有序链表

1.迭代（循环）+ 虚拟头结点

typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } else if(list2 == NULL) { return list1; } else{ ListNode* dum = (ListNode*)malloc(sizeof(ListNode)); ListNode* cur = dum; while(list1 && list2) { if(list1->val <= list2->val) { cur->next = list1; list1 = list1->next; } else{ cur->next = list2; list2 = list2->next; } cur = cur->next; } cur->next = list1 == NULL ? list2 : list1; return dum->next; } }

2.递归

typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } else if(list2 == NULL) { return list1; } else if(list1->val <= list2->val) { list1->next = mergeTwoLists(list1->next , list2); return list1; } else { list2->next = mergeTwoLists(list2->next , list1); return list2; } }