网站开发项目进度完成表,网站进入沙盒后,河南建设厅网站地址,知名门户网站题目#xff1a;
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。
方法#xff1a;分治#xff0c;类似于归并 class Solution {public ListNode mergeKLists(ListNode[] lists) {return mer…题目
给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
方法分治类似于归并 class Solution {public ListNode mergeKLists(ListNode[] lists) {return mergeKLists(lists, 0, lists.length);}private ListNode mergeKLists(ListNode[] lists, int i, int j) {int m j - i;if (m 0)return null; // 注意输入的 lists 可能是空的if (m 1)return lists[i]; // 注意输入的 lists 可能是空的ListNode left mergeKLists(lists, i, i m / 2);// 合并左半部分ListNode right mergeKLists(lists, i m / 2, j);// 合并右半部分return merge(left, right); }// 合并两个有序链表private ListNode merge(ListNode list1, ListNode list2) {ListNode dummy new ListNode(); // 用哨兵节点简化代码逻辑ListNode cur dummy; // cur 指向新链表的末尾while (list1 ! null list2 ! null) {if (list1.val list2.val) {cur.next list1; // 把 list1 加到新链表中list1 list1.next;} else { // 注相等的情况加哪个节点都是可以的cur.next list2; // 把 list2 加到新链表中list2 list2.next;}cur cur.next;}cur.next list1 ! null ? list1 : list2; // 拼接剩余链表return dummy.next;}}
