箭指Offer-合并两个排序的链表

解决方法

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
        ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
        {
            // 初始化：cur指向新链表的头结点， p1, p2分别指向链表l1, l2的头
            // 1.两个节点l1, l2，如果p1指向的节点值小于等于p2指向的节点,则cur->next=p1;cur++;p1++; 否则，cur->next=p2;p2++;cur++;
            // 2. 继续比较p1和p2， 若p1指向null，p2没有，则cur->next=p2;p2++;cur++;直到p2->null; 反之亦然
            ListNode* res=new ListNode(-1); // 初始化，创建新的结果链表
            ListNode* cur = res;
            if (pHead1==nullptr && pHead2== nullptr)
                return res->next;
            // 都没到末尾，直接比较
            while(pHead1!= nullptr && pHead2!= nullptr){
                if (pHead1->val<=pHead2->val)
                {
                    cur->next=pHead1;
                    cur = cur->next;
                    pHead1 = pHead1->next;
                } else if (pHead2->val<pHead1->val)
                {
                    cur->next = pHead2;
                    cur = cur->next;
                    pHead2 = pHead2->next;
                }
            }
            // 
            if (pHead1== nullptr){
                cur->next = pHead2;
            } else {
                cur->next = pHead1;
            }

            return res->next; // 结束，返回结果链表头指针
        }
};

个人难点

1. 第16、17行，创建链表的方法不熟，而且最终的返回值开始时不是结果链表的头指针，而实返回了最终位置指针
2. 第35~39行，没有想到用直接连起来的方式，链表的优势没有充分发挥出来。标答中的一行写法也值得学习。