Leetcode链表easy | 21.合并两个有序链表

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

示例：

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* h1=l1;   //  原有链表的动态指针
        ListNode* h2=l2;
        ListNode* node= new ListNode(0);   // 新建辅助节点，作为合并链表的暂时的头节点，最后需释放
        ListNode* current =node;  //  合并链表的动态指针
        
        while(h1&&h2){
            if(h1->val<=h2->val){
                current->next = h1;
                h1=h1->next;
                current=current->next;
            }  //  比较两个链表的节点的值，谁小，就接到合并链表的后面，动态指针后移
            else{
                current->next = h2;
                h2=h2->next;
                current=current->next;
            }
        }  //  等长部分的合并
        
        while(h1){
            current->next=h1;
            h1=h1->next;
            current=current->next;
        }  // 不等长部分的直接遍历连接到合并链表的后面
        
        while(h2){
            current->next=h2;
            h2=h2->next;
            current=current->next;
        }
        
        ListNode* ret=node->next;   //  暂时的头结点的后面一个节点作为合并完成的节点
        delete node;  //  释放
        return ret;
    }
};