148. Sort List

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next==null)
            return head;
        ListNode slow=head;
        ListNode fast=head, prev=head;
        while(fast!=null && fast.next!=null)
        {
            prev=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        prev.next=null;
        head = sortList(head);
        slow = sortList(slow);
        head = merge(head, slow);
        return head;
    }
    public ListNode merge(ListNode l1, ListNode l2)
    {
        
        ListNode l = new ListNode(0);
        ListNode temp=l;
        while(l1!=null && l2!=null)
        {
            if(l1.val > l2.val)
            {
                temp.next=l2;
                l2=l2.next;
            }
            else
            {
                temp.next=l1;
                l1=l1.next;
            }
            temp=temp.next;
        }
        if(l1!=null)
            temp.next=l1;
        if(l2!=null)
            temp.next=l2;
        return l.next;
    }
}