题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
W:
- 利用归并排序,把每个链表分开,用l1,l2接受,再两两合并
N: - 遇到数组,判断是否为空;
- 遇到链表,判断是否为空指针
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoList(ListNode* l1, ListNode* l2){ if(l1== nullptr){ return l2; } if(l2== nullptr){ return l1; } if(l1->val<=l2->val){ l1->next= mergeTwoList(l1->next,l2); return l1; } else{ l2->next= mergeTwoList(l1,l2->next); return l2; } } ListNode* mergeSort(vector<ListNode *> &lists,int l,int r){ if(l>=r){ return lists[l]; } int mid= l +(r-l)/2; ListNode* l1=mergeSort(lists,l,mid); ListNode* l2=mergeSort(lists,mid+1,r); return mergeTwoList(l1,l2);//分完就合并 } ListNode *mergeKLists(vector<ListNode *> &lists) { int len = lists.size(); if( len ==0 || lists[0]== nullptr ){ //一遇到链表首先想到去判断是否空,这里需要先判断大小 return nullptr; } return mergeSort(lists,0,len-1); } };