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

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


class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1=pHead1;
        ListNode* p2=pHead2;
        
        ListNode* dummyHead=new ListNode(0);
        ListNode* p3=dummyHead;
        
        //链表合并不会额外开辟新空间
        while(p1!=NULL&&p2!=NULL){
            if(p1->val<=p2->val){
                p3->next=p1; 
                p1=p1->next;
                p3=p3->next;
            }
            else{
                p3->next=p2;
                p2=p2->next;
                p3=p3->next;               
            }
        }
        
        if(p1==NULL){
           p3->next=p2; 
        }
        if(p2==NULL){
           p3->next=p1; 
        }
        
        return dummyHead->next;
    }
};

1. 只将被选中的链表和新链表步进。