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

package main

/*
 * 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
	}
	newListNode := new(ListNode)
	cur := newListNode

	for pHead1 != nil && pHead2 != nil {
		if pHead1.Val <= pHead2.Val {
			cur.Next = pHead1
			pHead1 = pHead1.Next
		} else {
			cur.Next = pHead2
			pHead2 = pHead2.Next
		}
		cur = cur.Next
	}
	if pHead1 == nil && pHead2 != nil {
		cur.Next = pHead2
	} else if pHead1 != nil && pHead2 == nil {
		cur.Next = pHead1
	}
	return newListNode.Next
}

// 递归版本
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(pHead1, pHead2.Next)
        return pHead2
    }
}