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

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

### 文章目录 ###

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

#### 传送门 ####

*  [Java版][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;
    }

##### 复杂度计算 #####

*  时间复杂度：O(m+n)
 *  空间复杂度：O(1)

[Java]: https://blog.csdn.net/symuamua/article/details/105647316