title: Leetcode 21.合并两个有序链表
hidden: true
tags:

• C++
• Leetcode
• 链表
• 优先队列
  categories: Leetcode
  mathjax: false
  date: 2019-05-04 19:56:44

题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

    输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

题目分析

通过自定义排序函数来使用优先队列来push所有节点后重新建立新链表返回, 这个方法可以用在多链表的题型中: Leetcode 23.合并K个排序链表.
一定要将最后的节点的next设为NULL!!!

源码

struct comp{ // 自定义比较函数
    bool operator()(ListNode* &a, ListNode* &b) { // 重载()运算符
        return a->val > b->val;
    }
};

class Solution {
public:
    priority_queue<ListNode*, vector<ListNode*>, comp> q; // 用优先队列储存节点

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL && l2 == NULL) return NULL; // 两个表都为空是返回空表
        ListNode* it = l1;
        while(it != NULL) { // 遍历l1链表将所有节点存到优先队列中
            q.push(it);
            it = it->next;
        }
        it = l2;
        while(it != NULL) { // 遍历l2链表将所有节点存到优先队列中
            q.push(it);
            it = it->next;
        }
        ListNode* res = q.top(); // 返回的头节点
        q.pop();
        it = res;
        while(q.size() != 0) {
            it->next = q.top();
            it = it->next;
            // cout<<"poped"<<endl;
            q.pop();
        }
        it->next = NULL; // ***将最后一个节点的next设为NULL***
        return res;
    }
};