这题就是merge sort的链表实现。
先看一下mergeSort:
public class myMergeSort {
static int number = 0;
public static void main(String[] args) {
int[] a = {26, 5, 98, 108, 28, 99, 100, 56, 34, 1, 45, 69};
printArray("排序前:", a);
MergeSort(a);
printArray("排序后:", a);
}
private static void printArray(String pre, int[] a) {
System.out.print(pre + "\n");
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + "\t");
System.out.println();
}
private static void MergeSort(int[] a) {
// TODO Auto-generated method stub
System.out.println("开始排序");
Sort(a, 0, a.length - 1);
}
private static void Sort(int[] a, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
//二路归并排序里面有两个Sort,多路归并排序里面写多个Sort就可以了
Sort(a, left, mid);
Sort(a, mid + 1, right);
merge(a, left, mid, right);
}
private static void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];
int r1 = mid + 1;
int tIndex = left;
int cIndex = left;
// 逐个归并
while (left <= mid && r1 <= right) {
if (a[left] <= a[r1])
tmp[tIndex++] = a[left++];
else
tmp[tIndex++] = a[r1++];
}
// 将左边剩余的归并
while (left <= mid) {
tmp[tIndex++] = a[left++];
}
// 将右边剩余的归并
while (r1 <= right) {
tmp[tIndex++] = a[r1++];
}
System.out.println("第" + (++number) + "趟排序:\t");
// TODO Auto-generated method stub
//从临时数组拷贝到原数组
while (cIndex <= right) {
a[cIndex] = tmp[cIndex];
//输出中间归并排序结果
System.out.print(a[cIndex] + "\t");
cIndex++;
}
System.out.println();
}
}
复杂度O(nlogn)。
这题的解法我看了https://leetcode.com/problems/sort-list/#/solutions
前半部分divide的递归部分比较难,后半部分就是merge two sorted lists。
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = new ListNode(-1);
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
//prev把slow前面那个node跟slow之间的link断开
prev.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return merge(l1, l2);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode node = new ListNode(-1);
ListNode l = node;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
l.next = l1;
l1 = l1.next;
} else {
l.next = l2;
l2 = l2.next;
}
l = l.next;
}
if (l1 != null) {
l.next = l1;
}
if (l2 != null) {
l.next = l2;
}
return node.next;
}
网友评论