题解 | #合并两个排序的链表#
合并两个排序的链表
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
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; } } };