Merge Two Sorted Lists

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, and should also be sorted.

For example, given following linked lists :

  5 -> 8 -> 20 
  4 -> 11 -> 15

The merged list should be :

4 -> 5 -> 8 -> 11 -> 15 -> 20

Method:

Create a dummy node, and keep adding smaller node to it.

Solution:

Time: O(n)
Space: O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode A, ListNode B) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        while (A != null && B != null) {
            if (A.val <= B.val) {
                prev.next = A;
                A = A.next;
            } else {
                prev.next = B;
                B = B.next;
            }
            prev = prev.next;
        }
        if (A != null) prev.next = A;
        if (B != null) prev.next = B;
        return dummy.next;
    }
}