这道题一看没有任何思路，就看别人的代码，发现getmid是一个比较巧妙地得到链表中中间节点的方法，其次在主函数中用到了递归，这样每一次合并就相当于一个归并排序，二路归并。
最后在merge函数中，合并两个链表，比如说，递归的最里层，合并两个节点，很巧妙的将已经加入列表的列表的值设为Integer.MAX_VALUE;这样就可以将没有合并到有序列表中的另一个有序链表合并进去。
public static ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode p = getMid(head);
ListNode q;
q = p.next;
p.next = null;
p = head;
p = sortList(p);
q = sortList(q);
return merge(p, q);
}
public static ListNode getMid(ListNode head) {
ListNode p = head;
ListNode q = head;
while (p.next != null && q.next != null && q.next.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
public static ListNode merge(ListNode p, ListNode q) {
ListNode r = new ListNode(0);
ListNode res = r;
while (p != null || q != null) {
int a,b;
if (p == null)
a = Integer.MAX_VALUE;
else
a = p.val;
if (q == null)
b = Integer.MAX_VALUE;
else
b = q.val;
if (a
京公网安备 11010802041100号