【LeetCode】21. 合并两个有序链表(Merge Two

点击 这里 跳转到LeetCode官网查看题目
点击 这里 跳转到LeetCode中国官网查看题目
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

中文:

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路：

• 对两有序链表按节点进行比较，较小的节点加入新链表中
• 当其中一个链表为空后，直接将剩下一个链表加入新链表尾部
• 体中需要不带头结点的链表，返回 newp -> next即可

Accept by C:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    //定义一个新链表
    struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode)), *newp;
    l3 -> val = 0;
    newp = l3;
    l3 -> next = NULL;
    //l1 、 l2 均非空 ，需要进行比较
    while(l1 != NULL && l2 != NULL){
        if(l1 -> val <= l2 -> val){
            //l1 接入 newp 尾部，工作指针l3向前移动
            l3 = l3 -> next = l1;
            l1 = l1 -> next;
        }else{
            l3 = l3 -> next = l2;
            l2 = l2 -> next;
        }
    }
    //l1 非空
    while(l1 != NULL){
        l3 = l3 -> next = l1;
        l1 = l1 -> next;
    }
    //l2非空
    while(l2 != NULL){
        l3 = l3 -> next = l2;
        l2 = l2 -> next;
    }
    //返回不带头节点的新链表
    return newp -> next;
}