leetcode sortList

Sort a linked list in O(n log n) time using constant space complexity.

/**

* Definition for singly-linked list.

* class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

* }

*/

class ListNode{

int val;

ListNode next;

ListNode(int x){

val = x;

next = null;

}

}

public class Solution {

public ListNode sortList(ListNode head) {

ListNode slow = head;

ListNode fast = head;

if(head == null){

return null;

}



ListNode pre = head;

while(slow.next!=null && fast.next!=null && fast!=null){

pre = slow;

slow = slow.next;

fast = fast.next.next;

}

pre.next = null;

ListNode res = mergesort(head,slow);

return res;

}



public ListNode mergesort(ListNode l1, ListNode l2){

if(l2 == null || l1 == l2){

return l1;

}

if(l1 == null){

return l2;

}

ListNode slow = l1;

ListNode fast = l1;

ListNode pre = l1;

while(slow.next!=null && fast.next!=null && fast!=null){

pre = slow;

slow = slow.next;

fast = fast.next.next;

}

pre.next = null;

ListNode head1 = mergesort(l1,slow);

slow = l2;

fast = l2;

pre = l2;

while(slow.next!=null && fast.next!=null && fast!=null){

pre = slow;

slow = slow.next;

fast = fast.next.next;

}

pre.next = null;

ListNode head2 = mergesort(l2,slow);

ListNode res = new ListNode(0);

ListNode cur = res;

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;

}

while(head1!=null){

cur.next = head1;

cur = cur.next;

head1 = head1.next;

}

while(head2!=null){

cur.next = head2;

cur = cur.next;

head2 = head2.next;

}

return res.next;

}

}

显示是runtime error, executed input为{}，可是我对于head == null的情形已经有return null的指令了呀……求助