一、题目

题目地址：

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

示例：

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

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

二、解法

1、解法1

思路：队列l1，l2，因为都是有序排列，所以，只需要，把l1作为基队列，将l2拼接到l1上面。

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    if pHead1 == nil {
        return pHead2
    }
    
    if pHead2 == nil {
        return pHead1
    }
    
    // 以pHead1为基准链表，保证最小值在 pHead1
    if pHead1.Val > pHead2.Val {
        pHead1, pHead2= pHead2, pHead1
    }
    
    tmp := pHead1
    for pHead2 != nil {
        if tmp.Next == nil {
            tmp.Next = pHead2
            
            return pHead1
        } else if pHead2.Val < tmp.Next.Val {
           // 将 p2从当前节点移除
            node2 := pHead2
            pHead2 = pHead2.Next
            
            // 将 p2节点插入 p2链表中
            node2.Next = tmp.Next
            tmp.Next = node2
            
            // 将p2 移动
            tmp = node2
        } else {
            tmp = tmp.Next
        }
    }
    
    return pHead1
}

2、递归版本

func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    if pHead1 == nil {
        return pHead2
    }
    
    if pHead2 == nil {
        return pHead1
    }
    
    if pHead1.Val < pHead2.Val {
        
        pHead1.Next = Merge(pHead1.Next, pHead2)
        return pHead1
    } else {
         pHead2.Next = Merge(pHead2.Next, pHead1)
        return pHead2
    }
}