[数据结构与算法]【剑指 Offer】 25. 合并两个排序的链表

1、题目描述

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

2、算法思想

1、首先新创一个链表，用来存储两个链表合并后的样子

2、再创建一个新的指针指向新链表

3、判断两个链表的大小，如果l1大，把l2放入新链表，令l2=l2->next;相反的，如果l2大于或等于l1，令l1=l1->next

4、放入较小的数据后，指针指向新链表的下一个

5、当两个链表不为空的时候，一直循环

6、因为可能存在两个链表不一样长，当有一个链表指到为空时，跳出while()循环

10、接下来判断l1、l2哪个链表不为空，将不为空的链表放在新链表的后面

3.代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *res = new ListNode(0);
        ListNode *p = res;
        while(l1!=nullptr && l2!=nullptr ){
            if(l1->val>=l2->val){
                p->next=l2;
                l2=l2->next;
            }else{
                p->next=l1;
                l1=l1->next;
            }
            p = p->next;              
        }
       
       p->next = l1 ? l1 : l2;
        return res->next;
    }
};