merge sort of linked lists(scratch)

 public class Linkedlist {

    public static class Node {

        int data;

        Node next;

        public Node(int data) {

            this.data = data;

            this.next = null;

        }

    }

    public static Node head;

    public static Node tail;

    public void addFirst(int data) {

        Node newNode = new Node(data);

        newNode.next = head;

        head = newNode;

    }

    public Node merge(Node head1, Node head2) {

        Node mergedLL = new Node(-1);

        Node temp = mergedLL;

        while (head1 != null && head2 != null) {

            if (head1.data <= head2.data) {

                temp.next = head1;

                head1 = head1.next;

                temp = temp.next;

            } else {

                temp.next = head2;

                head2 = head2.next;

                temp = temp.next;

            }

        }

        while (head1 != null) {

            temp.next = head1;

            head1 = head1.next;

            temp = temp.next;

        }

        while (head2 != null) {

            temp.next = head2;

            head2 = head2.next;

            temp = temp.next;

        }

        return mergedLL.next;

    }

    public Node mid(Node head) {

        // FIND MID

        Node slow = head;

        Node fast = head.next;

        while (fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    public Node mergeSort(Node head) {

        if (head == null || head.next == null) {

            return head;

        }

        Node mid = mid(head);

        Node righthead = mid.next;

        mid.next = null; // Disconnect the left half

        Node newleft = mergeSort(head);

        Node newright = mergeSort(righthead);

        return merge(newleft, newright);

    }

   

    public void print() {

        Node temp = head;

        while (temp != null) {

            System.out.print(temp.data);

            temp = temp.next;

        }

        System.out.println();

    }

    public static void main(String[] args) {

        Linkedlist ll = new Linkedlist();

        ll.addFirst(1);

        ll.addFirst(2);

        ll.addFirst(3);

        ll.addFirst(4);

        ll.addFirst(5);

        ll.print();

        ll.head = ll.mergeSort(ll.head);

        ll.print();

    }

}