leetcode之链表类之链表归并类-----OJ 2/21/23/445 链表相加求和 链表归并

本文主要是介绍leetcode之链表类之链表归并类-----OJ 2/21/23/445 链表相加求和 链表归并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、OJ21两个链表合并：两个链表合并可以简单的依次比较完成。

OJ21代码：

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (!l1 && !l2) {return nullptr;} else if (!l1 || !l2) {return l1?l1:l2;}ListNode *l3 = nullptr, *tail = l3;        while (l1 && l2) {int curval = (l1->val < l2->val)?l1->val:l2->val;if (l1->val < l2->val) {l1 = l1->next;} else {l2 = l2->next;}if (!l3) {l3 = new ListNode(curval);tail = l3;} else {ListNode *newnode = new ListNode(curval);tail->next = newnode;tail = newnode;}}while (l1) {int curval = l1->val;ListNode *newnode = new ListNode(curval);tail->next = newnode;tail = newnode;l1 = l1->next;}while (l2) {int curval = l2->val;ListNode *newnode = new ListNode(curval);tail->next = newnode;tail = newnode;l2 = l2->next;}return l3;}

2、OJ23多个链表合并

核心思路是：将多个链表加入到小顶堆，然后重载括号运算符重载(用于获取链表value并将较大取出，相当于比较运算符，这里要注意重载的方式)，每次取出堆顶，头节点将作为新链表的当前需加入的节点。

注意：1、小顶堆的每个元素是链表，因为每个链表已经有序，且每次堆调整会把头节点更小的链表调整到堆顶，故每次从取出的堆顶链表，取其头节点放入新链表即可，

   2、然后需要把这个链表去掉头节点的部分重新放入堆，以再次调整，找到头节点更小的链表，调整到堆顶。如果该链表已空，则无需加入。

   3、这样直到全部链表都已空，即结束。

OJ23代码：

    struct cmp {bool operator() (ListNode *a, ListNode *b) {return a->val > b->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {std::priority_queue<ListNode *, vector<ListNode *>, cmp> hp;for (auto l:lists) {if (l) {hp.push(l);}}ListNode *res = nullptr, *tail = res;if (hp.empty()) {return res;}while (!hp.empty()) {ListNode *top = hp.top();hp.pop();if (!res) {res = top;tail = res;} else {tail->next = top;tail = tail->next;}if (top->next) {hp.push(top->next);}}return res;}

3、OJ2 Add Two Numbers 和 OJ445 Add Two Numbers II

首先OJ2，如同两个链表的归并排序，两个链表从头开始value相加，注意进位的处理，直到只要有一个链表为空为止，然后对可能存在的不为空的链表继续累加，注意最后如果还有进位，还要追加一个value为1的节点；

OJ2代码：

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {        if (!l1 && !l2) {return nullptr;} else if (!l1 || !l2) {return (l1)?l1:l2;}ListNode *l3 = nullptr, *tail = nullptr;int add = 0;while (l1 && l2) {int v1 = l1->val, v2 = l2->val;int res = v1 + v2 + add;if (res >= 10) {add = 1;res = res - 10;} else {add = 0;}if (!l3) {l3 = new ListNode(res);tail = l3;} else {ListNode *newnode = new ListNode(res);tail->next = newnode;tail = newnode;}l1 = l1->next;l2 = l2->next;}while (l1) {int v = l1->val;int res = v + add;if (res >= 10) {add = 1;res = res - 10;} else {add = 0;}ListNode *newnode = new ListNode(res);tail->next = newnode;tail = newnode;l1 = l1->next;}while (l2) {int v = l2->val;int res = v + add;if (res >= 10) {add = 1;res = res - 10;} else {add = 0;}ListNode *newnode = new ListNode(res);tail->next = newnode;tail = newnode;l2 = l2->next;}if (add) {ListNode *newnode = new ListNode(1);tail->next = newnode;}return l3;}
};

对于OJ445，区别是需要先做原链表的翻转，然后再做OJ2的流程，也就是说数的顺序是反过来的

OJ445代码：

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {if (!l1 && !l2) {return nullptr;} else if (!l1 || !l2) {return l1?l1:l2;}ListNode *cur = l1, *prev = nullptr, *next = l1->next;while (next) {ListNode *nn = next->next;next->next = cur;cur->next = prev;prev = cur;cur = next;next = nn;}ListNode *rl1 = cur;cur = l2;prev = nullptr;next = l2->next;while (next) {ListNode *nn = next->next;next->next = cur;cur->next = prev;prev = cur;cur = next;next = nn;}ListNode *rl2 = cur;ListNode *rl3 = nullptr, *tail = nullptr;int add = 0;while (rl1 && rl2) {int v = rl1->val + rl2->val + add;if (v >= 10) {add = 1;v = v - 10;} else {add = 0;}if (!rl3) {rl3 = new ListNode(v);tail = rl3;} else {ListNode *newnode = new ListNode(v);tail->next = newnode;tail = newnode;}rl1 = rl1->next;rl2 = rl2->next;}while (rl1) {int v = rl1->val + add;if (v >= 10) {add = 1;v = v - 10;} else {add = 0;}ListNode *newnode = new ListNode(v);tail->next = newnode;tail = newnode;rl1 = rl1->next;}while (rl2) {int v = rl2->val + add;if (v >= 10) {add = 1;v = v - 10;} else {add = 0;}ListNode *newnode = new ListNode(v);tail->next = newnode;tail = newnode;rl2 = rl2->next;}if (add) {tail->next = new ListNode(1);}cur = rl3;prev = nullptr;next = cur->next;while (next) {ListNode *nn = next->next;next->next = cur;cur->next = prev;prev = cur;cur = next;next = nn;}return cur;}
};

这篇关于leetcode之链表类之链表归并类-----OJ 2/21/23/445 链表相加求和 链表归并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---