Topic link
https://leetcode.com/problems/merge-two-sorted-lists/
The questions in the original

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

The title translation
Merge the two ordered lists and return the new list. The new list should be the result of splicing two old lists.
Thinking method
Thinking a
After merging, the linked list is still in order. Two linked lists can be traversed at the same time. Each time, the nodes with smaller values in the two lists are selected and connected in turn to obtain the final linked list.
code

# 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
        """
        if not l1 or not l2:
            return l1 or l2
        head = cur = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return head.next

Idea 2
Similar idea one, you can take the linked list with a smaller head node as a reference, and insert the nodes in another linked list into the linked list according to the size, forming a large ordered linked list
code

# 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
        """
        if not l1 or not l2:
            return l1 or l2
        head = small = l1 if l1.val < l2.val else l2
        big = l1 if l1.val >= l2.val else l2
        pre = None
        while big:
            if not small:
                pre.next = big
                break
            if big.val >= small.val:
                pre = small
                small = small.next
            else:
                tmp = big.next
                pre.next = big
                pre = big
                big.next = small
                big = tmp
        return head

Thought three
Let’s think recursively.
code

# 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
        """
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/51529359