珠海网站建设 超凡科技,博远手机销售管理系统,门户网站规划,泉州免费网站制作题目
链接 描述 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 示例1 输入#xff1a; [{1,2,3},{4,5,6,7}] 返回值#xff1a; {1,2,3,4,5,6,7} 示例2 输入#xff1a; [{1,2},{1,4,5},{6}] 返回值#xff1a; {1,1,2,4,5,6}
题解#xff08;合并…题目
链接 描述 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 示例1 输入 [{1,2,3},{4,5,6,7}] 返回值 {1,2,3,4,5,6,7} 示例2 输入 [{1,2},{1,4,5},{6}] 返回值 {1,1,2,4,5,6}
题解合并
import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param lists ListNode类ArrayList* return ListNode类*/public ListNode mergeKLists (ArrayListListNode lists) {// write code herereturn divide(lists, 0, lists.size() - 1);}//两个链表合并public ListNode mergeTwoLists (ListNode list1, ListNode list2) {ListNode dummy new ListNode(0);ListNode cur dummy;while (list1 ! null list2 ! null) {if (list1.val list2.val) {cur.next list1;list1 list1.next;} else {cur.next list2;list2 list2.next;}cur cur.next;}cur.next list1 ! null ? list1 : list2;return dummy.next;}//将链表分成两半在合并//例如 从lists中取出list1,2,3,4,5,6 1,2合并成A 3,4合并成B 5,6合并成C 以此类推public ListNode divide (ArrayListListNode lists, int left, int right) {if (left right) {return null;}if (left right) {return lists.get(left);}int mid (left right) / 2;return mergeTwoLists(divide(lists, left, mid), divide(lists, mid 1, right));}
}
