LEETCODE 148: لیست مرتب سازی

/**
 * 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 previous = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            previous = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        previous.next = null;
        ListNode leftPart = sortList(head);
        ListNode rightPart = sortList(slow);
        ListNode merged = mergeLinkedList(leftPart, rightPart);
        return merged;
    }

    private ListNode mergeLinkedList(ListNode left, ListNode right) {
        if (left == null && right == null) {
            return null;
        }
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        ListNode leftPointer = left;
        ListNode rightPointer = right;
        ListNode result = new ListNode(0);
        ListNode current = result;
        while (leftPointer != null && rightPointer != null) {
            if (leftPointer.val <= rightPointer.val) {
                current.next = leftPointer;
                leftPointer = leftPointer.next;
                current = current.next;
            }
            else {
                current.next = rightPointer;
                rightPointer = rightPointer.next;
                current = current.next;
            }
        }
        if (leftPointer != null) {
            current.next = leftPointer;
                current = current.next;
        }
        else if (rightPointer != null) {
            current.next = rightPointer;
                current = current.next;
        }
        return result.next;
    }
}