21. 合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

class Solution {
public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode Dummy;
    ListNode *L = &Dummy;

    while (list1 && list2) {
      if (list1->val < list2->val) {
        L->next = list1;
        list1 = list1->next;
      } else {
        L->next = list2;
        list2 = list2->next;
      }
      L = L->next;
    }
    if (list1)
      L->next = list1;
    if (list2)
      L->next = list2;
    return Dummy.next;
  }
};

不得不说这个 Dummy 有时候还是该用就得用的。可以不 new，但很多时候不能不用，如果不用的话对于尾插法真的是非常麻烦而且绕人，没办法让 while 当中的操作统一，每次都要分支。

二刷

class Solution {
public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode Dummy;
    ListNode *This = &Dummy;
    while (list1 && list2) {
      if (list1->val < list2->val) {
        This->next = list1;
        list1 = list1->next;
      } else {
        This->next = list2;
        list2 = list2->next;
      }
      This = This->next;
    }
    if (list1)
      This->next = list1;
    if (list2)
      This->next = list2;
    return Dummy.next;
  }
};

这个当成模版背下来就行了，有用得很，凡是遇到需要归并的场景都会用到。

三刷

class Solution {
public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode Head(0, nullptr), *Prev = &Head;
    while (list1 && list2) {
      if (list1->val < list2->val) {
        Prev->next = list1;
        list1 = list1->next;
      } else {
        Prev->next = list2;
        list2 = list2->next;
      }
      Prev = Prev->next;
    }
    if (list1)
      Prev->next = list1;
    if (list2)
      Prev->next = list2;
    return Head.next;
  }
};

使用分离的 ListNode Head 节点和 ListNode *Prev 指针的关键点在于这是一种 detach 操作，也就是实际上 Prev 在第一次被赋值为 Prev->next 的时候已经一击脱离了。而如果给出的列表是空的，那么默认值 nullptr 也满足这一点，所以 Head 在经过任何操作之后永远指向的是表头。