链表内指定区间反转合并K个已排序的链表

链表内指定区间反转

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* 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个已排序的链表

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param lists ListNode类vector * @return ListNode类*/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;}
};