148. Sort List
Description
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Constraints
The number of nodes in the list is in the range
[0, 5 * 104].-105 <= Node.val <= 105
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input: head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Input: head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
Input: head = []
Output: []
Solutions
// 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;
}
}Follow up
Last updated
Was this helpful?