주어진 LinkedList를 정렬합니다.

/**
 * 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) {
        // using merge sort on the given list
        return merge(head);
    }

    public ListNode merge(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode middleNode = findMiddleNode(head);
        ListNode next = middleNode.next;
        middleNode.next = null;

        ListNode left = merge(head);
        ListNode right = merge(next);
        ListNode sortedNode = sort(left, right);
        return sortedNode;
    }

    public ListNode sort(ListNode l, ListNode r) {
        // base case
        if (l == null)
            return r;
        else if (r == null)
            return l;
        ListNode result = null;

        if (l.val < r.val) {
            result = l;
            result.next = sort(l.next, r);
        } else {
            result = r;
            result.next = sort(l, r.next);

        }
        return result;
    }

    public ListNode findMiddleNode(ListNode head) {
        if (head == null)
            return head;
        ListNode slow = head;
        ListNode faster = head;
        // 1>2>3>null
        // 1>2>null
        // null
        while (faster.next != null && faster.next.next != null) {
            slow = slow.next;
            faster = faster.next.next;
        }
        return slow;
    }
}