Merge two sorted lists

Question

There are many if-else conditions in my code

Question 1:

I am looking for suggestions to minimize if else conditions. Also, Code in Step 1 and Step2 is almost same. Is there any way to make it neat and improve readability

Question 2:

I am looking for suggestions to improve main method and which methods can be called with an instance or class variables. That technique I will apply to all my LinkedList related questions

---

public class MergeTwoSortedLists {

    public Node head;
    static class Node {
        int data;
        Node next;

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

    public void push(int data) {
        Node n = new Node(data);
        if ( head == null ) {
            head = n;
        } else {
            Node temp = head;
            while (temp.next != null ) {
                temp = temp.next;
            }
            temp.next = n;
        }
    }

    public static void printList(Node head) {
        Node temp = head;
        while ( temp != null ) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MergeTwoSortedLists l1 = new MergeTwoSortedLists();
        l1.push(1);
        l1.push(2);
        l1.push(13);
        l1.push(14);
        l1.push(50);
        printList(l1.head);

        MergeTwoSortedLists l2 = new MergeTwoSortedLists();
        l2.push(10);
        l2.push(20);
        l2.push(55);
        printList(l2.head);

        Node res = sortTwoLists(l1.head, l2.head);
        printList(res);

    }

    public static Node sortTwoLists(Node headA, Node headB) {
        Node s = null;
        Node res = null;
        if ( headA == null ) return headB;
        if ( headB == null ) return headA;

        /* Step 1: Set the s with less value */
        if ( headA!= null && headB!= null ) {
            if ( headA.data < headB.data ) {
                s = headA;
                headA = s.next;
            } else {
                s = headB;
                headB = s.next;
            }
        }
        res = s;

        /* Step2: Iterate oer two lists and keep moving s accordingly */
        while ( headA!= null && headB!= null ) {
            if ( headA.data < headB.data ) {
                s.next = headA;
                s = headA;
                headA = s.next;
            } else {
                s.next = headB;
                s = headB;
                headB = s.next;
            }
        }
        if ( headA == null ) {
            s.next = headB;
        }
        if ( headB == null ) {
            s.next = headA;
        }

        return res;

    }
}

Answer 1

General comments:

Your push method takes time proportional to the length of the list. Usually I would expect this method to take constant time. How can you change your data structure to achieve this?

Your push method could also check (in constant time) that the sorted order is preserved, and throw an exception if the client tries to push an illegal int.

Probably your class ought to be called SortedList, since this is the object you’re implementing. Then your sortTwoLists() (which could be called mergeTwoLists()) would be an instance method taking a SortedList object as a parameter. Note that both SortedLists involved are changed by this method.

printList() would probably be better as an instance method (in which case, it needn’t take any parameters).

Question 1: Here’s one possible approach. You could build an auxiliary MergingNode class, with instance variables:

Node mergedNode; // a node in the merged list
Node thisNode; // current node in the first list you’re merging
Node thatNode; // current node in the second list you’re merging

This class could have methods getMergedNode(), which just returns mergedNode, and nextMergeStep(), which replaces mergedNode by the next node in the merged list and updates either thisNode or thatNode, depending on which list we took a node from. Note that nextMergeStep() modifies the original SortedLists.

Then, Step 1 can be replaced by

SortedList merged = new SortedList();
MergingNode mergingNode = new MergingNode(null, headA, headB);
mergingNode.nextMergeStep();
merged.head = mergingNode.getMergedNode();

Step 2 can be replaced by

Node curNode = merged.head;
while (curNode != null) {
  mergingNode.nextMergeStep();
  Node nextNode = mergingNode.getMergedNode();
  curNode.next = nextNode;
  curNode = nextNode;
}

This way the nextMergeStep() method does all the work of your if statements.

Question 2: To clean up your main method, you could, for example, write a constructor for SortedList that takes an array of integers as a parameter, and constructs the SortedList containing those integers (meanwhile checking that the array was sorted).