package main

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

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	// special cases: [] []; [0] []; [] [0]
	if l1 == nil && l2 == nil {
		return nil
	}
	if l1 == nil && l2 != nil {
		return l2
	}
	if l1 != nil && l2 == nil {
		return l1
	}
	var curr *ListNode
	// decide which one is head
	if l1.Val < l2.Val {
		curr = l1
		l1 = l1.Next
	} else {
		curr = l2
		l2 = l2.Next
	}
	head := curr
	// merge 2 list until one of them is []
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			curr.Next = l1
			curr = l1
			l1 = l1.Next
		} else {
			curr.Next = l2
			curr = l2
			l2 = l2.Next
		}
	}
	// add tail
	if l1 != nil {
		curr.Next = l1
	} else {
		curr.Next = l2
	}
	return head
}