题解 | #合并两个排序的链表#

与合并有序数组的思路时一样的，先遍历两个链表共同的部分，再遍历其中某一个链表剩余的部分。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* i=pHead1;
        ListNode* j=pHead2;
        ListNode* head=new ListNode{-1};
        ListNode* k=head;
        while(i!=nullptr && j!=nullptr){
            if(i->val < j->val){
                k->next=i;
                i=i->next;
            }
            else{
                k->next=j;
                j=j->next;
            }
            k=k->next;
        }
        while(i!=nullptr){
            k->next=i;
            i=i->next;
            k=k->next;
        }
        while(j!=nullptr){
            k->next=j;
            j=j->next;
            k=k->next;
        }
        auto temp=head;
        head=head->next;
        delete temp;
        return head;
    }
};