Interview Classic 150 Problem P23: Merge K Sorted Linked Lists

---

Timeline

Timeline

2025-12-01

init

Divide and Conquer

---

Problem:

P23 MergeKsorted linked lists

https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-interview-150

Directly use a stack to implement the merge non-recursively.

struct ListNode {
	int val;
	ListNode *next;
	ListNode()
		: val(0)
		, next(nullptr)
	{
	}
	ListNode(int x)
		: val(x)
		, next(nullptr)
	{
	}
	ListNode(int x, ListNode *next)
		: val(x)
		, next(next)
	{
	}
};

#include <vector>
#include <queue>
using std::vector;
using std::queue;
class Solution {
    private:
	ListNode *merge2List(ListNode *l1, ListNode *l2)
	{
		ListNode dummy;
		ListNode *tail = &dummy, *tmp;
		while (l1 && l2) {
			if (l1->val < l2->val) {
				tmp = l1;
				l1 = l1->next;

			} else {
				tmp = l2;
				l2 = l2->next;
			}
			tail->next = tmp;
			tail = tail->next;
		}
		tail->next = l1 == nullptr ? l2 : l1;
		return dummy.next;
	}

    public:
	ListNode *mergeKLists(vector<ListNode *> &lists)
	{
		int n = lists.size();
		if (n == 0) {
			return nullptr;
		} else if (n == 1) {
			return lists[0];
		}
		queue<ListNode *> que;
		for (ListNode *&node : lists) {
			que.push(node);
		}
		ListNode *l1, *l2;
		while (que.size() != 1) {
			l1 = que.front();
			que.pop();
			l2 = que.front();
			que.pop();
			que.push(merge2List(l1, l2));
		}
		return que.front();
	}
};

leetcode hot 100 rewrite:

struct ListNode {
        int val;
        ListNode *next;
        ListNode()
                : val(0)
                , next(nullptr)
        {
        }
        ListNode(int x)
                : val(x)
                , next(nullptr)
        {
        }
        ListNode(int x, ListNode *next)
                : val(x)
                , next(next)
        {
        }
};

#include <vector>
using std::vector;

class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists)
        {
                int i, n = lists.size();
                ListNode dummy, *tail = &dummy, **curr_min;

                while (1) {
                        curr_min = nullptr;
                        for (ListNode *&p : lists) {
                                if (p == nullptr)
                                        continue;
                                if ((curr_min == nullptr) || ((*curr_min)->val > p->val))
                                        curr_min = &p;
                        }
                        if (curr_min == nullptr)
                                break;
                        tail->next = *curr_min;
                        tail = tail->next;
                        *curr_min = (*curr_min)->next;
                }
                return dummy.next;
        }
};