#!/usr/bin/env python3

__author__ = 'Wei Mu'

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        if l1 == None and l2 == None:
            return None
        
        ans = ListNode(0)
        p = ans
        p1 = l1
        p2 = l2
        
        while p1 != None or p2 != None:
            if p1 == None:
                while p2 != None:
                    p.next = p2
                    p2 = p2.next
                    p = p.next
                return ans.next
                
            if p2 == None:
                while p1 != None:
                    p.next = p1
                    p1 = p1.next
                    p = p.next
                return ans.next
                
            else:
                if p1.val <= p2.val:
                    p.next = p1
                    p1 = p1.next
                    p = p.next
                else:
                    p.next = p2
                    p2 = p2.next
                    p = p.next
        
        return ans.next
