/**
 * @Author:田宇寒.
 * @Date:Created in 9:56 2021年6月9日
 * @Description:合并两个有序链表
 * @ModifiedBy:
 * @Version: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class code21 {

 public class ListNode {
 int val;
 ListNode next;

 ListNode() {
 }

 ListNode(int val) {
 this.val = val;
 }

 ListNode(int val, ListNode next) {
 this.val = val;
 this.next = next;
 }
 }

 public ListNode mergeTwoListsWithIteration(ListNode l1, ListNode l2) {
 /**
 * create by: 田宇寒
 * description: 迭代算法 时间复杂度O(m+n) 空间复杂度O(1)
 * create time: 10:19 2021年6月9日
 * @Param: l1
 * @Param: l2
 * @return 'code21.ListNode'
 */
 ListNode head, tail;
 head = new ListNode(-1);
 tail = head;
 while (l1 != null && l2 != null) {
 if (l1.val <= l2.val) {
 tail.next = l1;
 l1 = l1.next;
 } else {
 tail.next = l2;
 l2 = l2.next;
 }
 tail = tail.next;
 }
 tail.next = l1 == null? l2 : l1;
 return head.next;
 }

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 /**
 * create by: 田宇寒
 * description: 递归算法 时间复杂度O(m+n) 空间复杂度O(m+n)
 * create time: 10:24 2021年6月9日
 * @Param: l1
 * @Param: l2
 * @return code21.ListNode
 */
 if (l1 == null) {
 return l2;
 } else if (l2 == null) {
 return l1;
 } else if (l1.val <= l2.val) {
 l1.next = mergeTwoLists(l1.next, l2);
 return l1;
 } else {
 l2.next = mergeTwoLists(l1, l2.next);
 return l2;
 }
 }
}