Cacher is the code snippet organizer for pro developers

public class Solution{
    public ListNode sortList(ListNode head){
        if(head == null || head.next == null) 
            return head;
        ListNode fast = head, slow = head;
        while(fast != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        slow = sortList(head);
        fast = sortList(fast);
        return merge(slow, fast);
    }
    public ListNode merge(ListNode slow, ListNode fast){
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(slow != null && fast != null){
            if(slow.val < fast.val) {
                cur.next = slow;
                slow = slow.next;
            }else {
                cur.next = fast;
                fast = fast.next;
            }
            cur = cur.next;
        }
        if(slow != null) {
            cur.next = slow;
        } else if(fast != null) {
            cur.next = fast;
        }
        return head.next;
    }
}

/**
 * Sort a linked list using insertion sort.
 */
 
 /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
 
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null)
            return head;
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE);
        ListNode prev = dummyHead, curr = head;
        while(curr != null){
            ListNode pre = findInsertPlace(prev, curr);
            ListNode originalNext = curr.next;
            curr.next = pre.next;
            pre.next = curr;
            curr = originalNext;
        }
        return dummyHead.next;
    }
    public ListNode findInsertPlace(ListNode p1, ListNode p2){
        ListNode prev = null, curr = p1;
        while(curr != null && curr.val <= p2.val){
            prev = curr;
            curr = curr.next;
        }
        return prev;
    }
    
}