Note:
谁小移谁
Key word:
public class Solution {
public ListNode merge(ListNode one, ListNode two) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (one != null && two != null) {
if (one.value < two.value) {
cur.next = one;
one = one.next;
} else {
cur.next = two;
two = two.next;
}
cur = cur.next;
}
if (one == null) {
cur.next = two;
}
if (two == null) {
cur.next = one;
}
return dummy.next;
}
}
Complexity Analysis:
TC: O(MAX(M,N)),需要遍历完最长的一支的所有结点,所以时间复杂度是MAX(M,N)
SC: O(1)