描述

示例

思路一：迭代

设置两个指针分别指向两个链表，依次将节点摘下比较，按值从小到大链接，直到某一条链表摘空，将零一链表剩余部分依次链接到链表末尾。

代码

    /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class Solution {
public:
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
    //write code here
    if(pHead1==nullptr) return pHead2;
    if(!pHead2) return pHead1; 
    ListNode* p=pHead1;
    ListNode* q=pHead2;
    ListNode* head=nullptr;
    ListNode* next=nullptr;
    if(pHead1->val>pHead2->val)  {next=head=pHead2; q=pHead2->next;}
    else {next=head=pHead1;p=pHead1->next;}
    while(p&&q)
    {
        if(p->val>q->val) 
        {
            next->next=q;
            next=q;
            q=q->next;
            next->next=nullptr;
        }
        else {

            next->next=p;
            next=p;
            p=p->next;
            next->next=nullptr;

        }
    }
    while(p) {next->next=p;next=p;p=p->next;next->next=nullptr;}
    while(q){
        next->next=q;next=q;q=q->next;next->next=nullptr;}
    return head;
    } 
} ;

思路二：迭代

特殊情况：如果有一个链表为空，返回另一个链表 如果pHead1 节点值比小pHead2，下一个节点应该是 pHead1，应该return pHead1，在return之前，指定pHead1的下一个节点应该是pHead1.next和pHead2俩链表的合并后的头结点 如果pHead1 节点值比pHead2大，下一个节点应该是pHead2，应该return pHead2，在return之前，指定pHead2的下一个节点应该是pHead1和pHead2.next俩链表的合并后的头结点.

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {

   if(pHead1==nullptr||pHead2==nullptr)
    {
        return pHead1!=nullptr?pHead1:pHead2;
    }
    if(pHead1->val<pHead2->val) 
    {
        pHead1->next=Merge(pHead1->next,pHead2);
        return pHead1;
    }
    else{
        pHead2->next=Merge(pHead1,pHead2->next);
        return pHead2;
    }
}
};