问题：将两个排序链表合并为一个新的排序链表

思路：将一个表作为原表，另一个作为node 来源，进行插入排序。

Python3

"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param two ListNodes
    @return a ListNode
    """
    def mergeTwoLists(self, l1, l2):
        head_node = l1
        
        if l1 == None or l2 == None:
            if l1 == None: return l2
            else: return l1
            
        while l2 != None:
            last_node = None
            l1 = head_node
            
            while l1 != None:
                # insert into the list
                if l2.val < l1.val:
                    # insert into the head of the list
                    if head_node == l1:
                        small_node = l2
                        # move forward
                        l2 = l2.next
                
                        small_node.next = l1
                        head_node = small_node
                        break
                    else:
                        small_node = l2
                        # move forward
                        l2 = l2.next
        
                        small_node.next = l1
                        print (head_node.val)
                        last_node.next = small_node
                        break
                else:
                    last_node = l1
                    l1 = l1.next
                    
            # insert into the tail of the list
            if l1 == None:
                large_node = l2
                # move forward
                l2 = l2.next
                large_node.next = None
                last_node.next = large_node
                
        return head_node

思考：对于这类问题，

1. 定方法（插入排序）
2. 分情况（表头插入，表中插入，表尾插入）
3. 合并各种情况（表头和表中插入可以合并成一种情况，即在较大的node之前插入。表尾插入则是在较小的node之后插入）
4. 编写

Java

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head_node = l1;
        ListNode last_node = null;
        ListNode small_node = null;
        ListNode large_node = null;
        // if this is a linked list null, then return non-null list
        if (l1 == null || l2 == null)
        {
            if (l1 == null)
            {
                return l2;
            }
            else
            {
                return l1;
            }
        }
        while (l2 != null)
        {
            l1 = head_node;
            last_node = null;
            while (l1 != null)
            {
                // insert into the list
                if (l2.val < l1.val)
                {
                    // insert into the head of the list
                    if (last_node == null)
                    {
                        small_node = l2;
                        l2 = l2.next;
                        small_node.next = l1;
                        head_node = small_node;
                        break;
                        
                    }
                    else
                    {
                        small_node = l2;
                        l2 = l2.next;
                        // link two nodes
                        last_node.next = small_node;
                        small_node.next = l1;
                        break;
                    }
                }
                else
                {
                    // refresh the last_node
                    last_node = l1;
                    // move forward
                    l1 = l1.next;
                }
            }
            // insert into the tail of the list
            if (l1 == null)
            {
                large_node = l2;
                l2 = l2.next;
                last_node.next = large_node;
                large_node.next = null;
                
            }
        }
        return head_node;
    }
}