Wrote a java code to merge two sorted linked lists in O(n) time complexity.

LLMergeSort.java

//Program to merge two sorted linked lists.

public class LLMergeSort{
    static Node head1;
    static Node head2;
    static Node newHead;

    static class Node{
        int data;
        Node next;

        Node(int d){data=d;next=null;}
    }

    public static void mergeSort(Node head1,Node head2){
        Node curr1 = head1;
        Node curr2 = head2;
        Node newHead = null;

        while(curr1!=null && curr2!=null){
            if(curr1.data<curr2.data){
                head1 = head1.next;
                curr1.next = newHead;
                newHead = curr1;
                curr1 = head1;
            }
            else{
                head2 = head2.next;
                curr2.next = newHead;
                newHead = curr2;
                curr2 = head2;
            }
        }

        if(curr1==null){
            while(curr2!=null){
                head2 = head2.next;
                curr2.next = newHead;
                newHead = curr2;
                curr2 = head2;
            }
        }
        else{
            while(curr1!=null){
                head1 = head1.next;
                curr1.next = newHead;
                newHead = curr1;
                curr1 = head1;
            }
        }
        reverseAndPrint(newHead);
    }

    private static void print(Node newHead){
        Node curr = newHead;

        System.out.println("The linked list after merging is : ");
        while(curr!=null){
            System.out.print("["+curr.data+"]->");
            curr = curr.next;
        }
        System.out.print("NULL");
        System.out.println();
    }

    public static void main(String[] args) {

        head1 = new Node(5);
        head1.next = new Node(6);
        head1.next.next = new Node(8);
        head1.next.next.next = new Node(11);

        head2 = new Node(2);
        head2.next = new Node(4);
        head2.next.next = new Node(7);
        head2.next.next.next = new Node(9);
        head2.next.next.next.next = new Node(13);

        mergeSort(head1,head2);
    }
}