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

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
    // 比较两个链表节点大小取小者，其中一个链表遍历完毕后，将另一个链表全部加入新链表表尾即可
    dummy := &ListNode{}
    tail := dummy

    for pHead1 != nil && pHead2 != nil {
        if pHead1.Val < pHead2.Val {
            tail.Next = pHead1
            tail = tail.Next
            pHead1 = pHead1.Next
        } else {
            tail.Next = pHead2
            tail = tail.Next
            pHead2 = pHead2.Next
        }
    }

    if pHead1 != nil {
        tail.Next = pHead1
        tail = tail.Next
    } 

    if pHead2 != nil {
        tail.Next = pHead2
        tail = tail.Next
    }

    return dummy.Next
}

1. 使用一个哑结点作为虚拟头结点，统一所有节点的处理方式；
2. 使用尾插法将两个链表当前节点中值较小的插入到新链表的表尾；
3. 如果其中一个链表已经处理完了，如果另一个链表还有剩余的元素，那么说明这些元素也是链表中较大的那部分；
4. 直接将这部分链接到链表表尾即可。