韩国网站模板,苏州免费推广的网站,北京到安阳火车票查询,2345网址导航智能主版文章目录 题目详情分析暴力求解两两合并链表 Java完整实现代码总结 题目详情
23 美团笔试真题 给你一个链表数组#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。 分析
暴力求解
将所有数值存入一个数组#xff… 文章目录 题目详情分析暴力求解两两合并链表 Java完整实现代码总结 题目详情
23 美团笔试真题 给你一个链表数组每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中返回合并后的链表。 分析
暴力求解
将所有数值存入一个数组然后数组排序按排序值新建一个链表
两两合并链表
由于链表有序可以先两两合并知道只剩一个链表即为有序链表
Java完整实现代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {int interval 1;int length lists.length;if(length 0) {return null;}if (length 1) {return lists[0];}while(interval length) {for (int i 0; i interval length; ){lists[i] merge2Lists(lists[i], lists[i interval]);i i interval*2;}interval interval * 2;}return lists[0];}public ListNode merge2Lists(ListNode L1, ListNode L2) {ListNode head new ListNode();ListNode tail head;while(L1 ! null L2 ! null) {if(L1.val L2.val) {tail.next L1;L1 L1.next;tail tail.next;} else {tail.next L2;L2 L2.next;tail tail.next;}}if(L1 null) {tail.next L2;} else {tail.next L1;}return head.next;}
}总结
两两合并链表是链表解题中常用的一个手段要牢记并灵活使用
