Merge two sorted linkedList

Question

I'm learning Data structures and came across this problem - merging two sorted linked list. I have gone through the recursive solution, and it seems pretty straight forward. I wanted to try an iterative solution and came up with this.

private static Node mergeListsIterative(Node headA, Node headB) {

        if (headA == null) {
            return headB;
        }

        if (headB == null) {
            return headA;
        }

        Node head;

        if (headA.data < headB.data) {
            head = headA;
            headA = headA.next;
        } else {
            head = headB;
            headB = headB.next;
        }

        Node temp = head;
        while (headA != null && headB != null) {
            if (headA.data < headB.data) {
                temp.next = headA;
                headA = headA.next;
            } else {
                temp.next = headB;
                headB = headB.next;
            }
            temp = temp.next;
        }

        if (headA == null) {
            temp.next = headB;
        } else {
            temp.next = headA;
        }

        return head;
    }

I saw this post on SO which uses an iterative approach. I feel that my code is simpler. Please review my code and tell me if it can be simplified.

Answer 1

There are two changes I would make in the code.

First and most important is replacing the comparision operator less-than < with less-or-equal <=. That would make your merging algorithm a correct part of a stable merge-sort: the nodes with equal keys (the node's data member) would preserve their relative order during merging.

The other one is renaming the temp variable to last, because that's what the variable actually identifies: the last item of the merged list under construction.

Answer 2

The name of the method is mergeLists, not mergeNodes. Even though you may think your method is simpler, using Nodes as parameters is misleading for the current method name. One way to address this issue is to rename the method as mergeListsUsingTheirHeads or, to be specific to the problem of merging sorted lists, mergeSortedListsUsingTheirHeads.

I have to ask: what made you think your code is simpler than that of the post you mentioned?