将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 方法一:递归
/** * Definition for singly-linked list. * 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; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null){ return list2; } if (list2 == null){ return list1; } else if (list1.val < list2.val){ list1.next = mergeTwoLists(list1.next,list2); return list1; } else { list2.next = mergeTwoLists(list1,list2.next); return list2; } } }
方法二:迭代
/** * Definition for singly-linked list. * 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; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode listNode = new ListNode(-1); ListNode pre = listNode; while(list2 != null && list1 != null){ if (list1.val < list2.val){ pre.next = list1; list1 = list1.next; } else { pre.next = list2; list2 = list2.next; } pre = pre.next; } pre.next = list1 == null? list2:list1; return listNode.next; } }