将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

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

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        hlist = None
        t1 = l1
        t2 = l2
        tlist = None
        if (not l1) and (not l2):
            return None
        while t1 or t2:
            if not hlist:
                hlist = ListNode(0)
                tlist = hlist
                if (not t1) or (not t2):
                    if t1:
                        return t1
                    if t2:
                        return t2
                if t1.val < t2.val:
                    tlist.val = t1.val
                    t1 = t1.next
                else:
                    tlist.val = t2.val
                    t2 = t2.next
            else:
                if t1 and t2:
                    if t1.val < t2.val:
                        tlist.next = t1
                        tlist = tlist.next
                        t1 = t1.next
                    else:
                        tlist.next = t2
                        tlist = tlist.next
                        t2 = t2.next
                else:
                    if t1:
                        tlist.next = t1
                        return hlist
                    if t2:
                        tlist.next = t2
                        return hlist
        return hlist

思路：比较两个链表的节点，小的就连接到新的链表中，然后小的节点往后移，大的节点不动，下次循环继续两个节点进行比较，直到某一个链表到链尾，然后剩下的直接连接到新的链表中，跳出循环结束。如果刚刚同时结束，则循环结束。

顺便给出我调试时写的两个函数：

def createl(l):
    h = None
    th = None
    for i in l:
        t = ListNode(0)
        if not h:
            h = t
            th = h
            t.val = i
        else:
            t.val = i
            th.next = t
            th = th.next
    return h

生成一个链表
参数l为一个list，返回一个链表的头节点

def printl(l):
    t = l
    while t:
        print str(t.val) + '->',
        t = t.next
    print '\n'

打印一个链表
参数l为一个链表的节点，一般是头节点

使用举例：

printl(create([1, 2, 3, 4, 5]))