合并两个排序的链表

---

题目：

题解：

1、哨兵节点

• 解题思路：设置一个哨兵节点，设置一个结点l指向哨兵节点，因为l1和l2是有序的，顺序比较l1和l2中节点的大小，使得l与之相连，最后返回哨兵的next即可！

• 复杂度分析：

  • 时间复杂度 O(M+N) ： M, N 分别为链表 l1, l2的长度，合并操作需遍历两链表。
  • 空间复杂度 O(1)

• 代码：

  class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
  }
  public class Solution {
      public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
          ListNode dummyHead = new ListNode(0);
          ListNode l = dummyHead;
          while (l1 != null && l2 != null) {
              if (l1.val < l2.val ) {
                  l.next = l1;
                  l1 = l1.next;
              }else {
                  l.next = l2;
                  l2 = l2.next;
              }
              l = l.next;
          }
          // 走到这里，说明l1或l2肯定有一个已经为null，故直接连接那个有的就ok了
          l.next = l1 != null ? l1 : l2;
          return dummyHead.next;
      }
  
  }