题解 | #合并两个排序的链表#

package main
import . "nc_tools"
/*
 * 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，找下一个较小值的节点
    if pHead1.Val < pHead2.Val { // 这就相当于移动 pHead1 与 pHead2 比较，返回值较小者
        pHead1.Next = Merge(pHead1.Next, pHead2)
        return pHead1
    } else {
        pHead2.Next = Merge(pHead1, pHead2.Next)
        return pHead2
    }
}

1. 使用递归的方式进行处理；
2. 如果有一个链表为空，那么下一个节点为另一个链表；
3. 如果 pHead1 节点值比 pHead2 节点值小，那么下一个节点是 pHead1 指向的节点，所以返回 pHead1，在返回 pHead1之前需要确定 pHead1 之后的节点，这个节点一定来自于 pHead1.Next 和 pHead2 中的一个（即这两个节点调用 Merge 函数合并后的头结点）；
4. 同理，如果 pHead1 节点值比 pHead2 节点值大，那么下一个节点是 pHead2 指向的节点，所以返回 pHead2，pHead2 之后的节点一定是 pHead1 与 pHead2.Next 调用 Merge 函数后合并后的头结点；
5. 最后一直向上层返回就可以链接其整条链了。