P18 合并两个有序链表

描述#

这个题目说的是，给你两个递增排序的链表，你要把它们合成一个链表，并且保持递增排序。另外要求，新链表上的节点使用的就是旧的两个链表上的节点，不能创建新节点。

比如说，给你的两个链表 L1 和 L2，分别是：
L1: 1 -> 3
L2: 2 -> 4 -> 6
合并后的链表就是：
1 -> 2 -> 3 -> 4 -> 6

代码#

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(m+n), Space: O(1)
  public ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }

    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
  }

}