合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

解法

 type ListNode struct {
    Val int
    Next *ListNode
 }

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 ==  nil {
		return list2
	}

	if list2 == nil {
		return list1
	}
	
	head := list1
	if list1.Val > list2.Val {
		head = list2
		list2 = list2.Next
	} else {
		list1 = list1.Next
	}

	tail := head

	for ;list1 != nil && list2 != nil; {
		if list1.Val <= list2.Val {
			tail.Next = list1
			tail = tail.Next
			list1 = list1.Next
		} else {
			tail.Next = list2
			tail = tail.Next
			list2 = list2.Next
		}
	}

	if list1 == nil {
		tail.Next = list2
	}

	if list2 == nil {
		tail.Next = list1
	}

	return head
}