148. Sort List
Last updated
Last updated
// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode mid = getMidNode(head);
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
private ListNode merge(ListNode list1, ListNode list2) {
ListNode tmpHead = new ListNode(0);
ListNode tail = tmpHead;
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = (list1 == null)? list2: list1;
return tmpHead.next;
}
private ListNode getMidNode(ListNode head) {
ListNode midPrev = null;
while(head != null && head.next != null) {
midPrev = (midPrev == null)? head: midPrev.next;
head = head.next.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}
}