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

2 Answers 2


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
    Commented Dec 11, 2015 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 and acknowledge you have read our privacy policy.