该题目来源于牛客网《剑指offer》专题。

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

Go语言实现：

//递归

func merge(list1, list2 *ListNode) *ListNode {

   if list1 == nil {

      return list2

   }

   if list2 == nil {

      return list1

   }

   var tempList *ListNode

   if list1.Val < list2.Val {

      tempList = list1

      tempList.Next = merge(list1.Next, list2)

   }

   if list1.Val > list2.Val {

      tempList = list2

      tempList.Next = merge(list1, list2.Next)

   }

   return tempList

}