C语言重构【21】合并两个有序链表-蒲公英云

C语言重构【21】合并两个有序链表

我就是我 2023-02-13 08:59 76阅读 0赞

文章目录

- - - 传送门
    - 题目
    - 方案：单链表练习
    - - 复杂度计算

传送门

Java版

题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

方案：单链表练习

/**
 * Definition for singly-linked list.
 * struct ListNode { 
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ 
    if(l1==NULL) return l2;
    else if(l2==NULL) return l1;
    struct ListNode* p;
    struct ListNode* head;
    if(l1->val<=l2->val){ 
        head = l1;
        l1 = l1->next;
    } else{ 
        head = l2;
        l2 = l2->next;
    }
    p  = head;
    while(l1!=NULL||l2!=NULL){ 
        if(l1==NULL) { 
            p->next = l2;
            return head;
        }else if(l2 == NULL){ 
            p->next = l1;
            return head;
        }else{ 
            //二者都不为空
            if(l1->val<=l2->val){ 
                    p->next = l1;
                    l1 = l1->next;
                    p = p->next;
                } else{ 
                    p->next = l2;
                    l2 = l2->next;
                    p = p ->next;
                }
        }
    }
    return head;
}