21-合并两个有序链表.md

思路： 1 首先两个链表都不能为nil，循环两个链表，把小的合并到新的链表中 2 合并以后，要判断一下list1和list2那个还有值，由于是有序的，则直接合并到newlist链表即可

type ListNode struct {
	Val  int
	Next *ListNode
}

func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    //创建 哑节点 作为 结果链表 的开头，返回结果是这个节点的下一个位置。目的是：在未遍历之前，我们不知道构建的结果中，开头元素到底是 l1 还是 l2, 为了让代码整齐，创建哑节点
	newList := &ListNode{0, nil}
	r := newList
	for list1 != nil && list2 != nil {
		if list1.Val > list2.Val {
			newList.Next = list2
			list2 = list2.Next
		} else {
			newList.Next = list1
			list1 = list1.Next
		}

		newList = newList.Next
	}

	if list1 != nil {
		newList.Next = list1
	}

	if list2 != nil {
		newList.Next = list2
	}

	return r.Next
}