Question
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
https://leetcode.com/problems/merge-two-sorted-lists/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 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; } cur.next = l1 == null ? l2: l1; return dummy.next; } }
|
Complexity:
Time complexity: O(n)
Space complexity: O(1)