Merge Sorted Linked List in Python using recursion

MergeSortedList.py

# A python script representing linked list


# A Node class. A single Node has a data and its next is NULL
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

class LinkedList:
  #initially an empty list so head is NULL
  def __init__(self):
    self.head = None

  #append at the end of the list
  def appendList(self, data):
    node = Node(data)
    if self.head == None:
      self.head = node
    else:
      curr = self.head
      while curr.next != None:
        curr = curr.next
    curr.next = node

  #append the node in sorted order
  def appendSorted(self, data):
    node = Node(data)
    curr = self.head
    prev = None

    while curr is not None and curr.data < data:
      prev = curr
      curr = curr.next
		
    if prev == None:
      self.head = node
    else:
      prev.next = node

    node.next = curr

  #print the list
  def printList(self):
    curr = self.head
    while curr != None:
      print ("%d->"%curr.data),
      curr = curr.next
    print "NULL"

  #merge linked list in sorted Order
  def mergeSorted(self, list1, list2):
    if list1 is None:
      return list2
    if list2 is None:
      return list1

    if list1.data < list2.data:
      temp = list1
      temp.next = self.mergeSorted(list1.next, list2)
    else:
      temp = list2
      temp.next = self.mergeSorted(list1, list2.next)
    return temp
					

list1 = LinkedList()
list1.appendSorted(13)
list1.appendSorted(12)
list1.appendSorted(3)
list1.appendSorted(16)
list1.appendSorted(7)

print("List 1 :"),
list1.printList()

list2 = LinkedList()
list2.appendSorted(9)
list2.appendSorted(10)
list2.appendSorted(1)

print("List 2 :"),
list2.printList()

list3 = LinkedList()
list3.head = list3.mergeSorted(list1.head, list2.head)

print("Merged List :"),
list3.printList()