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.
Analysis:
Make a dummy node, compare the two values in the two lists. If one is smaller, add it to the head. Update the head to next.
Note: the two lists may not be the same length. After all iteration, we need to check the lefts and add them to the result.
Time complexity: O(n)
Space complexity: O(1)
Code is below:
/** * 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) { // O(n) 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; } // Check if there're lefts if (l1 != null) { cur.next = l1; } if (l2 != null) { cur.next = l2; } return dummy.next; } }