1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ The OP has switched the lists when he checks the first node of the lists at the beginning. I could not think of any reason for that switch. Also he has avoided an else inside the while block which furthers added to MY confusion. So I thought the one which I have is much simpler. \$\endgroup\$ – v1shnu Oct 11 '17 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.