Merge two sorted linked lists (해커랭크)

링크

 

"""
 Merge two linked lists
 head could be None as well for empty list
 Node is defined as
 
 class Node(object):
 
   def __init__(self, data=None, next_node=None):
       self.data = data
       self.next = next_node

 return back the head of the linked list in the below method.
"""

def MergeLists(headA, headB):
    if (headA==None) | (headB==None):
        if(headA == None):
            return headB
        else:
            return headA
    if headA.data > headB.data:                  # headA points to the smaller one
        temp = headA
        headA = headB
        headB = temp
    head = headA
    curA = headA.next                         # curA one step ahead
    curB = headB
    while (curA!=None) & (curB!=None):
        if (curA.data>=curB.data):
            headB =headB.next
            curB.next = curA
            headA.next = curB
            headA = curA
            curA = curA.next
            curB = headB
        else:
            headA =curA
            curA = curA.next
    if curA == None:
        headA.next = headB
    return head