美团笔试题之合并 K 个升序链表

题目详情

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;}
}

总结

两两合并链表是链表解题中常用的一个手段，要牢记并灵活使用