题目难易程度： Easy

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

示例 1:

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

链表分单链表与双链表，还有环链表等形式，就单链表而言，链表结构的其他操作因在另外一张文章有写，在这里就不再多加叙述。
思路：目前本题的链表是升序链表，做法如下：使用递归完成本题。我做这两题都是用到递归，基本的套路一样。请认真观察，这个套路很好用。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        new_node_list = None
        if  l1 == None:
            return l2
        if l2 == None:
            return l1
        if  l1.val > l2.val:
            new_node_list = l2
            new_node_list.next = self.mergeTwoLists(l1,l2.next)
        else:
            new_node_list = l1
            new_node_list.next = self.mergeTwoLists(l1.next,l2)
        return new_node_list

我在上上个星期面试阿里的第一面面试时，上机操作的题目是：两个无续的链表，合并成一个有序的链表，步骤也操作，只是将两个无序链表排序，用上述的合并方法整合就行。以下是一种排序方法。我的写排序是 Leecode 第 148 题个人思路破解，该题难度：中等。

# 写法很简单的排序，但是占用内存空间上升。
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        list_tmp = []
        if head:
            while head.next:
                list_tmp.append(head.val)
                head = head.next
            list_tmp.append(head.val)

            list_data_sort = sorted(list_tmp)
            def nodeListSort(list_data_sort,i=0):
                new_list_node = None
                if i < len(list_data_sort):
                    new_list_node = ListNode(list_data_sort[i])
                    i += 1
                    new_list_node.next = nodeListSort(list_data_sort,i)
                return new_list_node
            return nodeListSort(list_data_sort)

做完上面那道题后，发现 Leecode 有类似的题目：

Leecode18. 删除链表的节点

题目难易程度： Easy
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        new_list_node = None
        if head.val == val:
            new_list_node = head.next
            return new_list_node
        else:
            new_list_node = head
            new_list_node.next = self.deleteNode(head.next, val)
        return new_list_node