078. 合并排序链表 c++

系统管理员 2022-09-15 05:51 78阅读 0赞

### 078. 合并排序链表 ###

*   *  题目描述
     *  解法

## 题目描述 ##

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = \[\[1,4,5\],\[1,3,4\],\[2,6\]\]  
输出：\[1,1,2,3,4,4,5,6\]  
解释：链表数组如下：  
\[  
1->4->5,  
1->3->4,  
2->6  
\]  
将它们合并到一个有序链表中得到。  
1->1->2->3->4->4->5->6  
示例 2：

输入：lists = \[\]  
输出：\[\]  
示例 3：

输入：lists = \[\[\]\]  
输出：\[\]

## 解法 ##

1.  两两合并

class Solution
    {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists)
        {
            int n = lists.size();
            if (n <= 0)
            {
                return NULL;
            }
            else if (n == 1)
            {
                return lists[0];
            }
    
            ListNode *p = lists[0];
            for (int i = 1; i < n; i++)
            {
                p = mergeTwo(p, lists[i]);
            }
    
            return p;
        }
        ListNode *mergeTwo(ListNode *head1, ListNode *head2)
        {
            if (head1 == NULL)
            {
                return head2;
            }
            if (head2 == NULL)
            {
                return head1;
            }
            ListNode root(0);
            ListNode *h = &root;
            while (head1 && head2)
            {
                if (head1->val < head2->val)
                {
                    h->next = head1;
                    head1 = head1->next;
                }
                else
                {
                    h->next = head2;
                    head2 = head2->next;
                }
                h = h->next;
            }
            if (head1)
            {
                h->next = head1;
            }
            if (head2)
            {
                h->next = head2;
            }
    
            return root.next;
        }
    };

1.  优先队列（小顶堆）

class Solution
    {
    public:
        struct cmp
        {
            bool operator()(ListNode *a, ListNode *b)
            {
                return a->val > b->val;
            }
        };
        ListNode *mergeKLists(vector<ListNode *> &lists)
        {
            int n = lists.size();
            if (n <= 0)
            {
                return NULL;
            }
            else if (n == 1)
            {
                return lists[0];
            }
            priority_queue<ListNode *, vector<ListNode *>, cmp> q;
            for (int i = 0; i < n; i++)
            {
                if(lists[i]) q.push(lists[i]);
            }
            ListNode root(0);
            ListNode *head = &root;
            ListNode *tmp;
            while (!q.empty())
            {
                tmp = q.top();
                q.pop();
                head->next = tmp;
                head = head->next;
                if (tmp->next)
                    q.push(tmp->next);
            }
    
            return root.next;
        }
    };