Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Iterative
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null){ if (l1.val < l2.val){ cur.next = l1; l1 = l1.next; }else{ cur.next = l2; l2 = l2.next; } cur = cur.next; } if (l1 != null){ cur.next = l1; }else{ cur.next = l2; } return dummy.next; } }
|
Recursive
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val){ l1.next = mergeTwoLists(l1.next, l2); return l1; }else{ l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
|