定制网站收费,wordpressμ,怀化优化网站排名,网站建设初学题目
输入k个排序的链表#xff0c;请将它们合并成一个排序的链表。
分析#xff1a;利用最小堆选取值最小的节点
用k个指针分别指向这k个链表的头节点#xff0c;每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步#xff0c;再比较k个指…题目
输入k个排序的链表请将它们合并成一个排序的链表。
分析利用最小堆选取值最小的节点
用k个指针分别指向这k个链表的头节点每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步再比较k个指针指向的节点并选取值最小的节点。重复这个过程直到所有节点都被选取出来。
解
public class Test {public static void main(String[] args) {ListNode listNode1 new ListNode(1);ListNode listNode2 new ListNode(2);ListNode listNode3 new ListNode(3);ListNode listNode4 new ListNode(4);ListNode listNode5 new ListNode(5);ListNode listNode6 new ListNode(6);ListNode listNode7 new ListNode(7);ListNode listNode8 new ListNode(8);ListNode listNode9 new ListNode(9);listNode1.next listNode4;listNode4.next listNode7;listNode2.next listNode5;listNode5.next listNode8;listNode3.next listNode6;listNode6.next listNode9;ListNode[] lists {listNode1, listNode2, listNode3};ListNode result mergeKLists(lists);while (result ! null) {System.out.println(result.val);result result.next;}}public static ListNode mergeKLists(ListNode[] lists) {ListNode dummy new ListNode(0);ListNode cur dummy;PriorityQueueListNode minHeap new PriorityQueue((n1, n2) - n1.val - n2.val);for (ListNode list : lists) {if (list ! null) {minHeap.offer(list);}}while (!minHeap.isEmpty()) {ListNode least minHeap.poll();cur.next least;cur least;if (least.next ! null) {minHeap.offer(least.next);}}return dummy.next;}
}分析按照归并排序的思路合并链表
输入的k个排序链表可以分成两部分前k/2个链表和后k/2个链表。如果将前k/2个链表和后k/2个链表分别合并成两个排序的链表再将两个排序的链表合并那么所有链表都合并了。合并k/2个链表与合并k个链表是同一个问题可以调用递归函数解决。
解
public class Test {public static void main(String[] args) {ListNode listNode1 new ListNode(1);ListNode listNode2 new ListNode(2);ListNode listNode3 new ListNode(3);ListNode listNode4 new ListNode(4);ListNode listNode5 new ListNode(5);ListNode listNode6 new ListNode(6);ListNode listNode7 new ListNode(7);ListNode listNode8 new ListNode(8);ListNode listNode9 new ListNode(9);listNode1.next listNode4;listNode4.next listNode7;listNode2.next listNode5;listNode5.next listNode8;listNode3.next listNode6;listNode6.next listNode9;ListNode[] lists {listNode1, listNode2, listNode3};ListNode result mergeKLists(lists);while (result ! null) {System.out.println(result.val);result result.next;}}public static ListNode mergeKLists(ListNode[] lists) {if (lists.length 0) {return null;}return mergeLists(lists, 0, lists.length);}private static ListNode mergeLists(ListNode[] lists, int start, int end) {if (start 1 end) {return lists[start];}int mid (start end) / 2;ListNode head1 mergeLists(lists, start, mid);ListNode head2 mergeLists(lists, mid, end);return merge(head1, head2);}private static ListNode merge(ListNode head1, ListNode head2) {ListNode dummy new ListNode(0);ListNode cur dummy;while (head1 ! null head2 ! null) {if (head1.val head2.val) {cur.next head1;head1 head1.next;}else {cur.next head2;head2 head2.next;}cur cur.next;}cur.next head1 null ? head2 : head1;return dummy.next;}
}
