链表内指定区间反转
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* dumy = new ListNode(0);
dumy->next = head;
ListNode* prev = nullptr;
ListNode* hh = dumy;
int skip = n - m;
while (m--) {
prev = hh;
hh = hh->next;
}
std::cout << hh->val << " ";
ListNode* tt = hh;
std::cout << skip << " ";
while(skip--)
tt = tt->next;
std::cout << tt->val << " ";
ListNode* tail = tt->next;
tt->next = nullptr;
prev->next = rever(hh);
hh->next = tail;
return dumy->next;
}
ListNode* rever(ListNode* head){
if(head == nullptr || head->next == nullptr) return head;
ListNode* newhead = rever(head->next);
head->next->next = head;
head->next = nullptr;
return newhead;
}
};
合并K个已排序的链表
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
return two(lists);
}
ListNode* two(vector<ListNode*>& lists)
{
int n = lists.size();
if(n == 0) return nullptr;
if(n == 1) return lists[0];
if(n == 2) return merge(lists[0], lists[1]);
vector<ListNode*> subleft(lists.begin(), lists.begin() + n/2);
vector<ListNode*> subright(lists.begin() + n/2, lists.end());
return merge(two(subleft), two(subright));
}
ListNode* merge(ListNode* L1, ListNode* L2){
auto dumy = new ListNode(0);
ListNode* head = dumy;
while (L1 && L2) {
if(L1->val < L2->val){
head->next = L1;
L1 = L1->next;
}else {
head->next = L2;
L2 = L2->next;
}
head = head->next;
}
head->next = L1 == nullptr ? L2 : L1;
return dumy->next;
}
};