面试题77：
问题：
输入一个链表的头节点，将该链表排序。
解决方案：
使用归并排序。将链表分为两个子链表，在对两个子链表排序后再将它们合并为一个排序的链表。
源代码：
/**
* 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 sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode head1 = head;
ListNode head2 = split(head);
head1 = sortList(head1);
head2 = sortList(head2);
return merge(head1,head2);
}
//从链表的中间分割链表并返回切割后的链表头。使用快慢指针，快指针走两步，慢指针走一步，当快指针到达链表尾时，慢指针到达链表中间节点。
private ListNode split(ListNode head){
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode second = slow.next;
slow.next = null;
return second;
}
//合并两个子链表
private 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?head1:head2;
return dummy.next;
}
}
面试题78：
问题：
输入k个排序的链表，将它们合并成一个排序的链表。
第一种方案（最小堆）：
解决方案：
使用最小堆。先扫描链表数组将所有排序链表的头节点添加到最小堆，然后将最小堆堆顶的链表节点弹出，因为最小堆堆顶的链表节点是整个堆中链表节点值最小的，弹出后再判断堆顶的链表节点是否存在下一个节点，如果存在就添加到最小堆，如果不存在就不需要添加，以此循环，直到堆中不存在元素。
源代码
/**
* 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) {
//创建哨兵节点
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
//创建最小堆，设置比较规则，链表节点值小的位于堆顶
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((p1,p2) -> p1.val - p2.val);
for(ListNode list:lists){
if(list != null){
minHeap.offer(list);
}
}
while(!minHeap.isEmpty()){
ListNode node = minHeap.poll();
cur.next = node;
cur = node;
if(node.next != null){
minHeap.offer(node.next);
}
}
return dummy.next;
}
}
第二种方案（归并排序）：
解决方案：
输入的k个排序链表可以分为两部分，前k/2个链表和后k/2个链表。如果将前k/2个链表和后k/2个链表分别再分为两个排序链表，再将两个排序链表合并，那么所有链表都合并了。
源代码：
/**
* 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) {
if(lists.length == 0){
return null;
}
return mergeLists(lists,0,lists.length);
}
//将k个排序链表分为前k/2个链表和后k/2个链表
private ListNode mergeLists(ListNode[] lists,int start,int end){
if(start + 1 == end){
return lists[start];
}
int mid = (start + end) / 2;
//前k/2个链表
ListNode head1 = mergeLists(lists,start,mid);
//后k/2个链表
ListNode head2 = mergeLists(lists,mid,end);
//将两个排序链表合并
return merge(head1,head2);
}
//将两个排序链表合并
private 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?head1:head2;
return dummy.next;
}
}
