package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func Merge(list1 *ListNode ,  list2 *ListNode ) *ListNode {
    sentry := &ListNode{Val: -1}
    prev := sentry
    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            prev.Next = list1
            list1 = list1.Next
        }else {
            prev.Next = list2
            list2 = list2.Next
        }
        prev = prev.Next
    }
    if list1 == nil {
        prev.Next = list2
    }else {
        prev.Next = list1
    }
    return sentry.Next
}