3/7—21. 合并两个有序链表

代index.php/tags-41973.html" >���实现：

方法1：递归  ---->难点

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* mergeTwoLists(struct ListNode *list1, struct ListNode *list2) {    /*        1.如果l1为空，返回l2        2.如果l2为空，返回l1        3.如果l1的值小于l2，比较l1的next值和l2，并把值赋给l1的下一个；返回l1        4.反之，比较l1和l2的next值，并把值赋给l2的下一个；返回l2    */    if (list1 == NULL) {        return list2;    } else if (list2 == NULL) {         return list1;    }    if (list1->val val) {         list1->next = mergeTwoLists(list1->next, list2);        return list1;    } else {        list2->next = mergeTwoLists(list1, list2->next);        return list2;    }}

方法2：常规解法+设置虚拟头结点                                                                           

/** * Definition for singly-linked list. * 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;    }    struct ListNode *head = malloc(sizeof(*head)); // 设置虚拟头结点    struct ListNode *h = head;    while (list1 && list2) {        if (list1->val val) {            h->next = list1;            list1 = list1->next;        } else {            h->next = list2;            list2 = list2->next;        }        h = h->next;        h->next = NULL;    }    if (list1) {        h->next = list1;    }    if (list2) {        h->next = list2;    }    struct ListNode *result = head->next;    head->next = NULL;    free(head);    return result;    }