[DLdigest-22] 合并两个有序链表

问题介绍

给定两个已经排好序的链表，将它们合并成为一个新的链表，例如链表a为1->2->4，链表b为1->3->4，合并后为1->1->2->3->4->4。

解决思路

因为两个链表都是各自已经排好序的，姑且认为从小到大的顺序。该问题比较容易解决，我们可以先考虑特殊情况，例如如果其中一个链表为空，则直接返回另一个链表；然后，我们先比较两个链表的第一个元素，取较小的元素为新的链表的起始指针；再对两个链表各自定义一个位置指针，将两个链表当前位置指针的值进行比较，取较小的指针作为新链表的下一个元素，并且更新原链表的指针位置；最后，当某个链表的位置指针为空时，则表明拼接结束。C++程序如下，我们默认已经定义好了ListNode结构体，结构体包含整形变量val以及同类型的结构体指针next，整个程序运行耗时8ms。

C++实现

/**
 * 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* tmpNode1=l1;
        ListNode* tmpNode2=l2;
        ListNode* firstNode;
        ListNode* currentNode;
        if(l1 == NULL)
            return l2;
        else if(l2==NULL)
            return l1;
        if((tmpNode1->val)<(tmpNode2->val)){
            firstNode=l1;
            tmpNode1=tmpNode1->next;
            firstNode->next=l2;
        }
        else{
            firstNode=l2;
            tmpNode2=tmpNode2->next;
            firstNode->next=l1;
        }
        currentNode = firstNode;
        
        while(tmpNode1!=NULL && tmpNode2!=NULL){
            if((tmpNode1->val) < (tmpNode2->val)){
                currentNode->next = tmpNode1;
                tmpNode1 = tmpNode1->next;
                currentNode = currentNode->next;
                currentNode->next = tmpNode2;
            }
            else{
                currentNode->next = tmpNode2;
                tmpNode2 = tmpNode2->next;
                currentNode = currentNode->next;
                currentNode->next = tmpNode1;
            }
        }
        return firstNode;
    }
};

往期推送：

[DLdigest-21] 检测括号字符串是否有效匹配

[DLdigest-20] 不同场景下的中文汉字转阿拉伯数字

[DLdigest-19] 不同场景下文本中的阿拉伯数字转中文汉字

[DLdigest-18] 电话号码的字母组合

[DLdigest-17] 3Sum Closest

[DLdigest-16] 3SUM

从信息论的角度来理解损失函数

从泰勒展开来看梯度下降算法