I have tried to merge two sorted lists into one and print that list using display method. But I am getting, I am getting this output:

-1 --> -21 --> 0 --> 2 --> 3 --> 5 --> 44 --> null

instead of:

-21 --> 0 --> 2 --> 3 --> 5 --> 44 --> null

Why am I getting this extra -1 before? I know that I have in line 15 ListNode dummy= new ListNode(-1); which I have initialized with -1. Is it the same -1 that I am getting? How do I skip this?

Here is my code :

public class Mergelists {
    private static ListNode head;

    private static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val){
            this.val= val;
            this.next= null;
        }
    }

        public static ListNode merge(ListNode l1, ListNode l2){
            ListNode dummy = new ListNode(-1);
            head = dummy;
            while (l1 != null && l2 != null){
                if (l1.val<l2.val){
                    dummy.next=l1;
                    l1=l1.next;
                }
                else
                {
                    dummy.next=l2;
                    l2=l2.next;
                }
                dummy=dummy.next;
            }
            if (l1 !=null)
                dummy.next=l1;
            if (l2 !=null)
                dummy.next=l2;

            return head.next;

        }
    public static void display() {
        ListNode current = head;
        while(current != null) {
            System.out.print(current.val   " --> ");
            current = current.next;
        }
        System.out.print("null");
    }


        public static void main(String[] args) {    

            ListNode head1 = new ListNode(-21);
            head1.next = new ListNode(3);
            head1.next.next = new ListNode(5);

            // -21->3->5 LinkedList created
            ListNode head2 = new ListNode(0);
            head2.next = new ListNode(2);
            head2.next.next = new ListNode(44);


            // 0->2->44 LinkedList created
            merge(head1, head2);

            display();
        }

CodePudding user response：

When method merge returns, the head of the list is still pointing to the dummy node.

You need to add this line before the return statement:

head = head.next;

But it's not the most serious mistake - head property, as well as all these methods, should not be static.

Modifier static means that the head node is being shared among all the instances of the list, which is not correct.

That will be the correct approach of implementing Singly Linked List. I also suggest you implement such methods as add() and remove().

class MyList {
    private ListNode head;
    
    private static class ListNode {
        private int val;
        private ListNode next;
        
        public ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }
    
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        head = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                dummy.next = l1;
                l1 = l1.next;
            } else {
                dummy.next = l2;
                l2 = l2.next;
            }
            dummy = dummy.next;
        }
        if (l1 != null)
            dummy.next = l1;
        if (l2 != null)
            dummy.next = l2;
        
        head = head.next;
        return head.next;
    }
    
    public void display() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val   " --> ");
            current = current.next;
        }
        System.out.print("null");
    }
    
    public static void main(String[] args) {
        MyList mergedList = new MyList();
        
        ListNode head1 = new ListNode(-21);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(5);
    
        // -21->3->5 LinkedList created
        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(44);
    
    
        // 0->2->44 LinkedList created
        mergedList.merge(head1, head2);
    
        mergedList.display();
    }
}

Output:

-21 --> 0 --> 2 --> 3 --> 5 --> 44 --> null

CodePudding user response：

The display method starts printing nodes from the class member variable head. In the merge method, head is initialized by -1, that's the reason why it always prints from -1. A simple way around would be to add an argument in the display method.

public static void display(ListNode head) {
        ListNode current = head;
        while(current != null) {
            System.out.print(current.val   " --> ");
            current = current.next;
        }
        System.out.print("null");
    }

Then store the result of merge method in a variable and call the display method from main method.

ListNode res= merge(head1, head2);
display(res);

CodePudding user response：

Your head is pointing to -1 which is dummy node. point your head to the next node.

 public static ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    head = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            dummy.next = l1;
            l1 = l1.next;
        } else {
            dummy.next = l2;
            l2 = l2.next;
        }
        dummy = dummy.next;
    }
    if (l1 != null)
        dummy.next = l1;
    if (l2 != null)
        dummy.next = l2;
   ##moving you head to next node.
    head = head.next;
    return head.next;

}