I have a method which will merger two sorted list together. The function works, but I saw some duplicated code.

Any ideas to make the code more elegant?

class Node(object):

   def __init__(self, data=None, next_node=None):
       self.data = data
       self.next = next_node

def MergeLists(headA, headB):
    head = tail = Node('',None)
    while headA or headB:

        # duplicated code here
        if headA is not None:
            if (headB and headA.data<=headB.data) or (headB is None):
                tail.next = headA
                tail = headA
                headA = headA.next

        if headB is not None:
            if (headA and headB.data <= headA.data) or (headA is None):
                tail.next = headB
                tail = headB
                headB = headB.next

    return head.next

Elegance is in the eye of the beholder; the following (replacing the duplicated code here part) is certainly less redundant:

for i in xrange(2):
    if headA is not None:
        if ( headB and headA.data<=headB.data) or (headB is None):
            tail.next = headA
            tail = headA
            headA = headA.next
    # When i==0, this will flip headA & headB
    # When i==1, it will restore them
    headA,headB = headB,headA
  • \$\begingroup\$ I think the MergeLists function will not work. \$\endgroup\$ – Ray Dec 11 '15 at 2:52

In python it is common to name variables and functions using snake_case, so I would suggest calling your variables stuff like head_a and merge_lists.

Your solution is destructive in the sense that it modifies the original lists, which usually is not a good option. So here is a solution which firstly as long as both lists has elements it picks the lower element. This accounts for the curr_a and (... curr_a.data <= curr_b.data) part of the first condition in the code below.

Secondly when either list empties out, we need to empty the list with more elements. This accounts for the curr_a and (not curr_b ...) of the condition. If only curr_a has values, the not curr_b is also True, and it enters the first part, if curr_a == False however, it goes to the else: part. Just as expected.

The resulting code, which doesn't modify the original lists:

def merge_lists(curr_a, curr_b):
    """Merge curr_a and curr_b into a new list leaving originals intact."""

    # Create a temporary first node    
    head = result = Node()

    # Merge elements into a new list
    while curr_a or curr_b:
        if curr_a and (not curr_b or curr_a.data <= curr_b.data):
            result.next = Node(curr_a.data)
            curr_a = curr_a.next
            result.next = Node(curr_b.data)
            curr_b = curr_b.next

        result = result.next

    return head.next

And this is a rather neat, simple and elegant solution for merging the two lists.


Your Answer

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