MergeSort on LinkedList in JAVA

I decided to implement the MergeSort. LinkedList is preferred for MergeSort over an Array because it does not require a lot of random access, and a LinkedList does not require adjacent or unnecessary memory allocation.

public static LinkNode mergeSort(LinkNode head) {
    if (head == null || head.next == null) return head;
    LinkNode cur = head;
    int size = 0;

    while (cur != null) {
        size++;
        cur = cur.next;
    }

    LinkNode left = head;
    LinkNode right = null;
    int mid = size >> 1;
    cur = left;

    while (mid > 1) {
        cur = cur.next;
        mid--;
    }

    right = cur.next;
    cur.next = null;

    return merge(mergeSort(left), mergeSort(right));
}

public static LinkNode merge(LinkNode left, LinkNode right) {
    if (left == null) return right;
    if (right == null) return left;

    LinkNode head = (left.data < right.data) ? left : right;

    while (left != null && right != null) {
        if (left != null && left.next.data < right.data) {
            left = left.next;
        }
        else {
            LinkNode temp = left.next;
            left.next = right;
            right = temp;
            left = left.next;
        }
    }

    return head;
}

This article is my 9th oldest. It is 180 words long, and it’s got 0 comments for now.