Open Shawngbk opened 7 years ago
Solved by mergesort
/**
} */ public class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; //split list into two parts ListNode slow = head, fast = head, prev = null; while(fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } //将两链断开 prev.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(slow);
return merge(l1, l2);
}
private ListNode merge(ListNode l1, ListNode l2) { ListNode l = new ListNode(0), p = l; while(l1 != null && l2 != null) { if(l1.val < l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } p = p.next; } if(l1 != null) { p.next = l1; } if(l2 != null) { p.next = l2; } return l.next; } }
Solved by mergesort
/**
} */ public class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; //split list into two parts ListNode slow = head, fast = head, prev = null; while(fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } //将两链断开 prev.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(slow);
}
private ListNode merge(ListNode l1, ListNode l2) { ListNode l = new ListNode(0), p = l; while(l1 != null && l2 != null) { if(l1.val < l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } p = p.next; } if(l1 != null) { p.next = l1; } if(l2 != null) { p.next = l2; } return l.next; } }