Merge two linked lists in Python

Question

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

Answer 1

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

• Ray: I think the MergeLists function will not work.

Answer 2

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
 else:
 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.