LeetCode 之路

LeetCode 23 ——合并 K 个排序链表

2018-10-22  本文已影响9人  seniusen

1. 题目

23

2. 解答

2.1. 方法一
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        int k = lists.size(); // 链表个数
        
        if (k >= 2)
        {   
            // 先将前两个链表合并为一个新链表,再把新链表依次和后面的链表合并
            ListNode *head = mergeTwoLists(lists[0], lists[1]);
            for (int i = 2; i < k; i++)
            {
                head = mergeTwoLists(head, lists[i]);
            }
            
            return head;  
        }
        else if (k == 1)
        {
            return lists[0];
        } 
        else
        { 
            return NULL;
        }
        
    }
    
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        ListNode *head = new ListNode(0); // 新建哨兵结点,方便操作
        ListNode *temp = head;
        
        // 依次比较两个链表的结点值,将值较小的结点插入到新建的链表后面
        while(l1 && l2)
        {
            if (l2->val <= l1->val)
            {
                temp->next = l2;
                temp = temp->next;
                l2 = l2->next;
            }
            else
            {
                temp->next = l1;
                temp = temp->next;
                l1 = l1->next;
            }
        }
        
        // 其中一个链表比较完毕,将另外一个链表剩余结点直接插入到新建的链表后面
        if (l1)
        {
            temp->next = l1;
        }
        else
        {
            temp->next = l2;
        }
        
        temp = head;
        head = head->next;// 删除哨兵结点
        delete(temp);
        
        return head;  
    }
};
2.2. 方法二
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        int k = lists.size(); // 链表个数
        
        if (k >= 2)
        {   
            while(k != 1) // 循环合并过程直到剩余一个链表
            {
                if (k % 2 == 0)  // 总共偶数个链表,依次合并相邻两个链表然后从前往后放到 vector 中去
                {
                    for (int i = 0; i < k; i=i+2)
                    {
                        lists[i / 2] = mergeTwoLists(lists[i], lists[i+1]);
                    }
                    k = k / 2; // 每次合并后的新链表个数
                }
                
                else // 总共奇数个链表,依次合并相邻两个链表然后从前往后放到 vector 中去,最后余一个链表直接放入 vector 最后面
                {
                    for (int i = 0; i < k - 1; i=i+2)
                    {
                        lists[i / 2] = mergeTwoLists(lists[i], lists[i+1]);
                    }
                    lists[k / 2] = lists[k-1];
                    k = k / 2 + 1; // 每次合并后的新链表个数
                }
            }
            
            return lists[0]; 
                  
        }
        else if (k == 1)
        {
            return lists[0];
        } 
        else
        { 
            return NULL;
        }
        
    }
    
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        ListNode *head = new ListNode(0); // 新建哨兵结点,方便操作
        ListNode *temp = head;
        
        // 依次比较两个链表的结点值,将值较小的结点插入到新建的链表后面
        while(l1 && l2)
        {
            if (l2->val <= l1->val)
            {
                temp->next = l2;
                temp = temp->next;
                l2 = l2->next;
            }
            else
            {
                temp->next = l1;
                temp = temp->next;
                l1 = l1->next;
            }
        }
        
        // 其中一个链表比较完毕,将另外一个链表剩余结点直接插入到新建的链表后面
        if (l1)
        {
            temp->next = l1;
        }
        else
        {
            temp->next = l2;
        }
        
        temp = head;
        head = head->next;// 删除哨兵结点
        delete(temp);
        
        return head;  
    }
};
2.3. 方法三
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        int k = lists.size();
        
        struct cmp
        {
            bool operator()(ListNode* a, ListNode* b)
            {
                return a->val > b->val;
            }
        };

        priority_queue<ListNode *, vector<ListNode*>, cmp> q; // 构建小顶堆

        for (int i = 0; i < k; i++)
        {
            if (lists[i])
                q.push(lists[i]);  // 链表非空,加入队列
        }

        ListNode *head = new ListNode(0); // 新建哨兵结点,方便操作
        ListNode *temp = head;

        while(!q.empty())
        {
            temp->next = q.top(); // 将元素值最小的首结点插入到新链表后面
            temp = temp->next; // 指针后移
            q.pop();        // 首结点元素值最小的链表出队
            if (temp->next)  // 把删除首结点后的链表放入队列中
                q.push(temp->next);
        }

        temp = head;
        head = head->next;
        delete(temp);  // 删除哨兵结点

        return head;
    }
};

获取更多精彩,请关注「seniusen」!


seniusen
上一篇下一篇

猜你喜欢

热点阅读