package code;

import java.util.ArrayList;
import java.util.List;

/*
 * 148. Sort List
 * 
 * Medium
 * Linked List, Sort
 * merge
 *      
 *      ListNode
 *      https://www.cnblogs.com/morethink/p/8452914.html
 * TipsO(1)
 */
public class lc148 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode sortList(ListNode head) {
        if( head==null || head.next == null ){
            return head;
        }
        ListNode slow = head;   //
        ListNode fast = head.next;
        while( fast!=null && fast.next!=null ){   //
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode l2 = sortList(slow.next);
        slow.next = null;   //
        ListNode l1 = sortList(head);
        return mergeList(l1, l2);
    }

    public ListNode mergeList(ListNode l1, ListNode l2){
        ListNode res = new ListNode(0);
        ListNode head = res;
        while( l1!=null && l2!=null ){
            if(l1.val