Merge two linked lists in Python

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

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.