合并两个排序的链表

题目来源

www.acwing.com/problem/content/34/

题目

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

样例

1
2
3

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

输出：1->2->3->4->5->5

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
        newNode->next = NULL;
        
        ListNode* nodeL1 = l1;
        ListNode* nodeL2 = l2;
        ListNode* endNode = newNode;
        while(nodeL1!= NULL&&nodeL2!=NULL){
            
            if(nodeL1->val<= nodeL2->val){
                endNode->next = nodeL1;
                endNode = nodeL1;
                nodeL1 = nodeL1->next;
            }else{
                endNode->next = nodeL2;
                endNode = nodeL2;
                nodeL2 = nodeL2->next;
            }
        }
        
        if(nodeL1!=NULL){
            endNode->next = nodeL1;
        }else if(nodeL2!=NULL){
            endNode->next = nodeL2;
        }else{
            endNode->next = NULL;
        }
        return newNode->next;
    }
};