这个问题需要与归并排序排两个名单，基本思路分为切割与合并
合并后的代码Merge Two Sorted List里已经讲得非常清楚了。
所以这里直接给出代码。
public ListNode merge(ListNode l1, ListNode l2) {
ListNode helper = new ListNode(0);
ListNode runner = helper;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
runner.next = l1;
l1 = l1.next;
runner = runner.next;
} else {
runner.next = l2;
l2 = l2.next;
runner = runner.next;
}
if (l1 != null)
runner.next = l1;
if (l2 != null)
runner.next = l2;
}
return helper.next;
}切割的思想非常重要，在数组里面是通过切割知道仅仅剩下一个元素的时候结束，链表也一样。
数组中推断仅仅有一个元素的方法是if(left==right)
链表中推断仅仅有一个元素的方法是if(head.next==null)
数组中的切割的方法是
int middle = (left + right) / 2;
mergeSort(array, left, middle);
mergeSort(array, middle + 1, right);
merge(array, left, middle, right);
链表中怎么找middle呢？这个时候我们想起了前面所提到的Walker_Runner技术来找中点。
ListNode walker = head;
ListNode runner = head;
while (runner.next != null && runner.next.next != null) {
walker = walker.next;
runner = runner.next.next;
}
ListNode head2 = walker.next;
walker.next = null;
head = mergeSort(head);
head2 = mergeSort(head2);
return merge(head, head2);
以下给出完整的代码
public ListNode sortList(ListNode head) {
if (head == null)
return head;
return mergeSort(head);
}
public ListNode mergeSort(ListNode head) {
if (head.next == null)
return head;
ListNode walker = head;
ListNode runner = head;
while (runner.next != null && runner.next.next != null) {
walker = walker.next;
runner = runner.next.next;
}
ListNode head2 = walker.next;
walker.next = null;
head = mergeSort(head);
head2 = mergeSort(head2);
return merge(head, head2);
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode helper = new ListNode(0);
ListNode runner = helper;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
runner.next = l1;
l1 = l1.next;
runner = runner.next;
} else {
runner.next = l2;
l2 = l2.next;
runner = runner.next;
}
if (l1 != null)
runner.next = l1;
if (l2 != null)
runner.next = l2;
}
return helper.next;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。