问题：将两个排序链表合并为一个新的排序链表
思路：将一个表作为原表，另一个作为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
思考：对于这类问题，
- 定方法（插入排序）
- 分情况（表头插入，表中插入，表尾插入）
- 合并各种情况（表头和表中插入可以合并成一种情况，即在较大的node之前插入。表尾插入则是在较小的node之后插入）
- 编写
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;
}
}
