Recursive merge sort of two Linked Lists using third reference

Question

I am trying to solve the recursive merge sort using the third reference. I wanted to take a third reference and keep on linking the nodes from the two linked lists (two linked lists are individually sorted) in the sorted order without creation of any extra node.

I see that there is a recursive program referenced here. But I wanted to try this using the third reference but I keep on messing this up. Could anyone let me know what condition am I missing here?

import java.util.ArrayList;
import java.util.ListIterator;

public class MergeLinkedListsIntoExisting {
    public static void main(String[] args){
        Node nodeList1 = null, nodeList2 = null;
        Node temp = null;
        ArrayList<Integer> array1 = new ArrayList<Integer>();
        array1.add(3);
        array1.add(7);
        array1.add(9);

        ArrayList<Integer> array2 = new ArrayList<Integer>();
        array2.add(1);
        array2.add(2);
        array2.add(8);

        nodeList1 = add(nodeList1, array1);
        nodeList2 = add(nodeList2, array2);
        System.out.println("**List 1**");
        print(nodeList1);
        System.out.println("**List 2**");
        print(nodeList2);
        System.out.println("Sorted List");
        Node nodeList3 = mergeTwoLists(nodeList1, nodeList2, temp);
        print(nodeList3);
    }
    private static Node add(Node node, ArrayList<Integer> list){
        Node current = node;
        Node head = node;
        ListIterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            if(head==null){
                head = new Node();
                head.data = it.next();
                head.next=null;
                node = head;
            }
            else{
                current = new Node();
                current.data = it.next();
                current.next = null;
                node.next = current;
                node = node.next;
            }
        }
        return head;
    }

    private static void print(Node node) {
        if(node!=null){
            while(node.next!=null){
                System.out.print(node.data + " ");
                node = node.next;
            }
            System.out.println(node.data);
        }
        else{
            System.out.println("No elements in the linkedList.");
        }
    }


    private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
        if(nodeList1 == null) return nodeList2;
        if(nodeList2 == null) return nodeList1;

        if(nodeList1.data <= nodeList2.data){
            if(temp == null){
                temp = nodeList1;
                temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp.next);
            }
            else{
                System.out.println(temp.data);
                temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp.next);
            }
        }else{
            if(temp == null){
                temp = nodeList2;
                System.out.println(temp.data);
                temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp.next);
            }
            else{
                System.out.println(temp.data);
                temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp.next);
            }
        }
        return temp;
    }
}

The resolution should be with temp.next in the recursive call of mergeTwoLists. Correct me and my approach as required.

Daniel Nugent · Accepted Answer · 2015-04-01T17:18:08.743

Edit: I just looked at this again, and I think the main modification that fixed the code was just removing the special cases for temp equals null.

I just modified your code and got it working. Just pass through temp instead of temp.next, and you don't need to special case if temp is null.

import java.util.ArrayList;
import java.util.ListIterator;

public class MergeLinkedListsIntoExisting {
    public static void main(String[] args){
        Node nodeList1 = null, nodeList2 = null;
        Node temp = null;
        ArrayList<Integer> array1 = new ArrayList<Integer>();
        array1.add(3);
        array1.add(7);
        array1.add(9);

        ArrayList<Integer> array2 = new ArrayList<Integer>();
        array2.add(1);
        array2.add(2);
        array2.add(8);

        nodeList1 = add(nodeList1, array1);
        nodeList2 = add(nodeList2, array2);
        System.out.println("**List 1**");
        print(nodeList1);
        System.out.println("**List 2**");
        print(nodeList2);
        System.out.println("Sorted List");
        Node nodeList3 = mergeTwoLists(nodeList1, nodeList2, temp);
        print(nodeList3);
    }
    private static Node add(Node node, ArrayList<Integer> list){
        Node current = node;
        Node head = node;
        ListIterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            if(head==null){
                head = new Node();
                head.data = it.next();
                head.next=null;
                node = head;
            }
            else{
                current = new Node();
                current.data = it.next();
                current.next = null;
                node.next = current;
                node = node.next;
            }
        }
        return head;
    }

    private static void print(Node node) {
        if(node!=null){
            while(node.next!=null){
                System.out.print(node.data + " ");
                node = node.next;
            }
            System.out.println(node.data);
        }
        else{
            System.out.println("No elements in the linkedList.");
        }
    }


    private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
        if(nodeList1 == null) return nodeList2;
        if(nodeList2 == null) return nodeList1;

        if(nodeList1.data <= nodeList2.data){

          temp = nodeList1;
          temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp);

        }else{

          temp = nodeList2;
          temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);                
        }
        return temp;
    }
}

public class Node{
    int data;
    Node next;
}

why do we need to exchange the parameters? nodeList2.next in place of nodeList1 and vice versa? However the condition is there to route it to the proper if branch, then why do we need to exchange it so? — Deepak, Apr 01 '15 at 17:14
@Deepak I realized today that switching the parameters is actually not necessary. I just modified the answer. — Daniel Nugent, Apr 01 '15 at 17:16
Now there will be no confusion to the other viewers. Thanks for the edit! — Deepak, Apr 01 '15 at 18:18

score 0 · Answer 2 · answered Apr 01 '15 at 07:04

0

If you want recursive method< then try this

private static Node mergeTwoLists(Node nodeList1, Node nodeList2) {
    if(nodeList1 == null) return nodeList2;
    if(nodeList2 == null) return nodeList1;
    Node tmp = new Node();
    if(nodeList1.data <= nodeList2.data){
        tmp.data = nodeList1.data;
        tmp.next = mergeTwoLists(nodeList1.next, nodeList2);
    }else{
        tmp.data = nodeList2.data;
        tmp.next = mergeTwoLists(nodeList1, nodeList2.next);
    }
    return temp;
}

answered Apr 01 '15 at 07:04

Mikhail Kasparyan

135
2

I wanted to see how to resolve my approach. There are many examples to do recursive way as mentioned (hyperlink) in the question. All I am checking to see is what is the mess I am doing in my program. Thanks anyways, your way is also a nice approach though. – Deepak Apr 01 '15 at 07:14

Recursive merge sort of two Linked Lists using third reference

2 Answers2