You are given two single linked lists A and B (essentially, you are given pointers to the head nodes of A and B), such that the lists themselves are sorted (A is sorted in increasing order, and B is sorted in increasing order). Your goal is to combine two lists and output a new single linked list C (essentially, you should output a pointer to its head node) such that contains all elements of A UB (A union B) in increasing order. As an example, consider the following inputs: A: 1 48 10 11 20 B:-5 18+920 The corresponding output that you should return is: C:-5+14+8+9+10 11 20 Your algorithm must run in time 0(max([A], [B]) and use only 0(1) space (in addition to its inputs). When your algorithm terminates, inputs A and B may be destroyed; so do not try to preserve the input and waste time for it. For each linked list node, you can get the integer associated with it by its . val member, and its next node by its next member, where next is null for the last node. You do not have and need tail pointers; you only have pointers to head nodes