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)