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

W:

• base case

  • 若两链表有一个为空，返回非空链表，递归结束；

• 从头结点开始考虑，比较两表头结点的值，值较小的list的头结点后面接merge好的链表（进入递归了）；

• 当前层不考虑下一层的细节，当前层较小的结点接上该结点的next与另一结点merge好的表头就可以了；

• 递归会为我们将这些链表节点连接好返回，我们需要明确这个函数的功能

• 每次的返回值：排序好的链表头；

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1== nullptr){
            return pHead2;
        }
        if(pHead2== nullptr){
            return pHead1;
        }
        if(pHead1->val<pHead2->val){
            pHead1->next=Merge(pHead1->next,pHead2);
            return pHead1;
        }
        else{
            pHead2->next = Merge(pHead1,pHead2->next);
            return pHead2; 
        }
    }
};