现在位置: 首页 / 学习 / leetcode / 正文

LeetCode第二十三题：合并 K 个升序链表

  • admin
  • 学习
  • 2024-03-18
  • 73热度
  • 0评论

题目来源：LeetCode第二十三题

1.题目描述

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

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

示例 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

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

2.解题思路

解法一：暴力法

  • 描述：遍历每个链表的每个节点，将节点的值收集到一个数组中。使用排序算法（如快速排序、归并排序等）对收集到的所有值进行排序。遍历排序后的数组，为每个值创建一个新的链表节点，并将这些节点依次连接起来形成一个新的有序链表。
  • 时间复杂度：O(NlogN)。最主要的开销来自于排序步骤。
  • 空间复杂度：O(N)。
  • 参考代码：

java版：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 存储所有节点的值
        List<Integer> values = new ArrayList<>();
        // 遍历所有链表
        for (ListNode list : lists) {
            while (list != null) {
                // 将当前节点的值添加到列表中
                values.add(list.val);
                // 移动到下一个节点
                list = list.next;
            }
        }
        // 将所有值排序
        Collections.sort(values);
        // 创建一个哑节点作为合并后链表的起始节点
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        for (int value : values) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }

        return dummy.next;
    }

}

C++版：

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		// 存储所有节点的值
		vector<int> values;
		// 遍历所有链表
		for (ListNode* list : lists) {
			while (list != nullptr) {
				// 将当前节点的值添加到列表中
				values.push_back(list->val);
				// 移动到下一个节点
				list = list->next;
			}
		}
		// 将所有值排序
		sort(values.begin(), values.end());
		// 创建一个哑节点作为合并后链表的起始节点
		ListNode dummy(0);
		ListNode* tail = &dummy;
		// 根据排序后的值创建新链表
		for (int value : values) {
			tail->next = new ListNode(value);
			tail = tail->next;
		}

		return dummy.next;
	}
};

C版：

// 比较函数，用于qsort
int compare(const void* a, const void* b) {
	return (*(int*)a - *(int*)b);
}

// 合并多个链表的函数
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
	int* values = (int*)malloc(10000 * sizeof(int)); // 假设所有链表总节点数不超过10000
	int count = 0; // 用于记录值的总数
	for (int i = 0; i < listsSize; ++i) {
		struct ListNode* list = lists[i];
		while (list != NULL) {
			values[count++] = list->val; // 收集值
			list = list->next;
		}
	}

	qsort(values, count, sizeof(int), compare); // 对值进行排序

	struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
	dummy->val = 0;
	dummy->next = NULL;
	struct ListNode* current = dummy;
	for (int i = 0; i < count; ++i) {
		struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
		node->val = values[i];
		node->next = NULL;
		current->next = node;
		current = current->next;
	}

	free(values); // 释放动态分配的数组
	return dummy->next; // 返回合并后的链表的头节点
}

解法二：顺序合并法

  • 描述：开始时，我们有一个空链表或者将第一个链表视为已合并的链表。依次将每个链表与当前已合并的链表合并。具体来说，第一步中，我们可能将第一个链表视为初始的已合并链表，然后从第二个链表开始逐个与之合并；或者从空链表开始，逐个合并所有链表。每一次合并两个链表都是通过比较两个链表的当前节点值，选择较小的节点加入到已合并链表的末尾，并移动对应的指针，直到所有节点都被合并。重复操作，直到所有链表都被合并进已合并的链表中。
  • 时间复杂度：O(k2n)。O(∑i=1k​(i×n))=O(2(1+k)⋅k​×n)=O(k2n)。
  • 空间复杂度：O(1)。
  • 参考代码：

java版：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 边界情况处理：如果输入的数组为空，返回null
        if (lists == null || lists.length == 0)
            return null;
        // 初始化merged链表为null，用于后续合并
        ListNode merged = null;
        // 遍历lists数组，逐一将每个链表合并到merged中
        for (int i = 0; i < lists.length; i++) {
            merged = mergeTwoLists(merged, lists[i]);
        }
        return merged;
    }
    // 辅助函数：合并两个有序链表

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个哑节点，这样可以避免单独处理头节点为空的情况
        ListNode dummy = new ListNode(0);
        // tail始终指向当前合并链表的末尾节点
        ListNode tail = dummy;
        // 当两个链表都不为空时，选择较小的节点追加到tail后，并移动对应链表的指针
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            // 移动tail到合并链表的最后一个节点
            tail = tail.next;
        }
        // 如果l1或l2中的一个还有剩余节点，直接将其追加到合并链表的末尾
        tail.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }

}

C++版：

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		// 边界情况处理：如果输入的数组为空，返回null
		if (lists.empty()) return nullptr;
		// 初始化merged链表为null，用于后续合并
		ListNode* merged = nullptr;
		// 遍历lists数组，逐一将每个链表合并到merged中
		for (ListNode* list : lists) {
			merged = mergeTwoLists(merged, list);
		}
		return merged;
	}

private:
	// 辅助函数：合并两个有序链表
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		// 创建一个哑节点，这样可以避免单独处理头节点为空的情况
		ListNode dummy;
		// tail始终指向当前合并链表的末尾节点
		ListNode* tail = &dummy;
		// 当两个链表都不为空时，选择较小的节点追加到tail后，并移动对应链表的指针
		while (l1 && l2) {
			if (l1->val < l2->val) {
				tail->next = l1;
				l1 = l1->next;
			}
			else {
				tail->next = l2;
				l2 = l2->next;
			}
			// 移动tail到合并链表的最后一个节点
			tail = tail->next;
		}
		// 如果l1或l2中的一个还有剩余节点，直接将其追加到合并链表的末尾
		tail->next = l1 ? l1 : l2;
		return dummy.next;
	}
};

C版：

// 函数：合并两个有序链表
// 输入：l1 和 l2，分别指向两个有序链表的头节点
// 返回：合并后有序链表的头节点
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
	// 创建一个哑节点作为结果链表的起始节点，便于处理边界情况
	struct ListNode dummy;
	struct ListNode* tail = &dummy; // tail用于追踪结果链表的末尾
	dummy.next = NULL; // 初始化哑节点的next指针

	// 当两个链表均非空时，比较当前节点的值，并将较小的节点接到结果链表的末尾
	while (l1 && l2) {
		if (l1->val < l2->val) {
			tail->next = l1; // 将l1的当前节点接到tail后面
			l1 = l1->next; // 移动l1到下一个节点
		}
		else {
			tail->next = l2; // 将l2的当前节点接到tail后面
			l2 = l2->next; // 移动l2到下一个节点
		}
		tail = tail->next; // 更新tail到结果链表的最新末尾节点
	}

	// 如果某一链表已完全合并而另一链表还有剩余节点，直接将剩余部分接到结果链表的末尾
	tail->next = l1 ? l1 : l2;

	return dummy.next; // 返回哑节点的下一个节点，即合并后链表的头节点
}

// 函数：顺序合并k个排序链表
// 输入：lists指向链表数组的指针，listsSize表示链表数组的大小
// 返回：合并后有序链表的头节点
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
	if (listsSize == 0) return NULL; // 如果数组为空，直接返回NULL

	struct ListNode* mergedList = NULL; // 初始化结果链表为NULL
	for (int i = 0; i < listsSize; ++i) {
		// 顺序合并：依次将当前链表lists[i]合并到mergedList中
		mergedList = mergeTwoLists(mergedList, lists[i]);
	}
	return mergedList; // 返回合并后的链表
}

解法三：分治法

  • 描述：将原问题分解为若干个规模较小的相同问题。具体到合并 k 个排序链表，即将 k 个链表分成两半，分别对这两半的链表应用相同的合并逻辑。递归地解决这些子问题。如果子问题规模足够小，则直接解决。在本问题中，当分解到只有一个或两个链表时，使用合并两个有序链表的方法来直接解决。将子问题的解合并成原问题的解。对于链表合并，将上述分解得到的两部分链表的解（即各自合并后的链表）再合并成一个链表。
  • 时间复杂度：O(knlogk)。
  • 空间复杂度：O(logk)。
  • 参考代码：

java版：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null; // 边界情况处理
        }
        return merge(lists, 0, lists.length - 1); // 调用分治合并函数
    }

    // 分治合并函数
    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        // 递归合并左半部分链表
        ListNode l1 = merge(lists, left, mid);
        // 递归合并右半部分链表
        ListNode l2 = merge(lists, mid + 1, right);
        // 合并两个有序链表
        return mergeTwoLists(l1, l2);
    }

    // 合并两个有序链表的函数
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        // 处理剩余节点
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

C++版：

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		// 处理空列表的边界情况
		if (lists.empty()) return nullptr;
		return merge(lists, 0, lists.size() - 1);
	}
private:
	// 分治合并函数
	ListNode* merge(vector<ListNode*>& lists, int left, int right) {
		// 当只剩一个链表时，直接返回
		if (left == right) return lists[left];
		// 计算中点
		int mid = left + (right - left) / 2;
		// 递归合并左半部分链表
		ListNode* l1 = merge(lists, left, mid);
		// 递归合并右半部分链表
		ListNode* l2 = merge(lists, mid + 1, right);
		// 合并两个有序链表
		return mergeTwoLists(l1, l2);
	}
	// 合并两个有序链表的函数
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode dummy;
		ListNode* tail = &dummy;
		while (l1 && l2) {
			if (l1->val < l2->val) {
				tail->next = l1;
				l1 = l1->next;
			}
			else {
				tail->next = l2;
				l2 = l2->next;
			}
			tail = tail->next;
		}
		tail->next = l1 ? l1 : l2;
		return dummy.next;
	}

};

C版：

// 声明辅助函数
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2);

// 分治合并函数，递归地将链表数组分为两半，然后合并
struct ListNode* merge(struct ListNode** lists, int left, int right) {
	// 当左右边界相遇时，递归结束
	if (left == right) {
		return lists[left];
	}

	int mid = left + (right - left) / 2;
	struct ListNode* l1 = merge(lists, left, mid);
	struct ListNode* l2 = merge(lists, mid + 1, right);
	return mergeTwoLists(l1, l2);
}

// 分治合并k个链表的主函数
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
	// 处理边界情况
	if (listsSize == 0) return NULL;
	if (listsSize == 1) return lists[0];

	return merge(lists, 0, listsSize - 1);
}

// 合并两个有序链表的辅助函数
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
	struct ListNode dummy, * tail = &dummy;
	dummy.next = NULL;

	while (l1 && l2) {
		if (l1->val < l2->val) {
			tail->next = l1;
			l1 = l1->next;
		}
		else {
			tail->next = l2;
			l2 = l2->next;
		}
		tail = tail->next;
	}

	tail->next = l1 ? l1 : l2;
	return dummy.next;
}