2018/12/02 - Merge Two Sorted Li

将两个链表进行合并是算法中常见的操作，简单的合并操作容易实现。但是更多的情况是链表通常是按照一定顺序排列的，合并的时候也需要考虑合并后其中各个元素的排列问题。这可以归类为合并两个有序链表的问题，具体来说就是：有两个单向链表，它们的每个节点都有一个数字，且节点中的数字按照升序排列，现在需要合并这两个链表，合并后仍然是按照升序排列，如下图所示：

对于这个问题，最直接的思路应该是直接进行合并，然后再对合并后的链表进行排序。

虽然这个方法是可行的，但是这个方法并不是最好的，这个方法主要的耗时在于重新排序，它的时间复杂度是O（m+n）log（m+n），m和n分别是L1和L2链表的长度，稍后我们会给出更加优雅的方案以供讨论。

在提出第二种方案之前，需要提一下可能会用到的一个“trick” — 虚拟节点（dummy node），也叫虚拟头节点。虚拟节点是当我们合并两个链表时不知道哪个节点是新链表第一个节点时会用到，因为要确保新链表的第一个元素最小，而这个元素可能是 l1 或 l2 第一个节点中的某一个。所以，暂时用虚拟节点作为新链表的起始节点，后面合并完毕后会删除这个节点。

对于我们之前提到的这个问题，我们会用到两个指针 （指向链表第一个节点）、（指向链表第一个节点），前面提到的虚拟节点和当前节点（current node，用于循环，被初始化指向虚拟节点）。通过循环访问所有节点来构成新的链表。在每次循环中，会比较两个链表中和指向的节点的值，使当前节点一直指向较小值节点的下一节点。如下图：

在第一步中，指向的节点值为 2，指向节点值为 6, 因为 2 < 6，所以curr 指向 所指向的那个值为 2 的节点，然后指向下一节点，即指向节点值为 5 的节点，如下图：

第二步中，指向的节点的值仍然小于指向的节点的值，所以 curr 继续向后移动指向节点值为 5 的节点，指向下一节点, 即指向节点值为 7 的节点如下图：

第三步中，指向的节点的值总算是大于指向的节点的值了，那么在这个时候要注意了, curr 该向哪里移动呢？想一想。

需要注意代码实现 curr 的一次移动时候，要先让 curr 当前指向的 node 的 next 指向 所指向的节点, curr->next = p2。

然后执行 curr = curr->next

curr 该移动到当前指向的节点，然后向后移动，如下图：

以此类推，直到或者指针移动到链表的末端，因为我们在每次比较中都选择较小的值，所以当或者中任何一个指针指向链表末端，代表另外一个没有还没到达末端的链表的后序的值都比已到达末端的链表中最大的值要大，所以只需要将后续的节点追加到新的链表后即可。

代码实现如下：

// Definition for singly-linked list.
struct ListNode {
   int val;
   ListNode *next;

   // 结构体的构造函数，与类的构造函数相同。不适用于 C 语言结构体。
   // 冒号后面的是初始化列表，也就是给成员val初始化为传入的参数x，next初始化为NULL 
   ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
   // 参数为 l1 和 l2 的头节点地址
   ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {

       // 如果链表 l1 为空，直接返回 l2
       if (l1 == nullptr)
           return l2;
       
       // 如果链表 l2 为空，直接返回 l1
       if (l2 == nullptr)
           return l1;

       // 设置虚拟节点 ，并初始化值为 -1，指针域为 空。
       // new ListNode(-1) 返回的地址赋值给 ListNode类型 的指针 h
       ListNode* h = new ListNode(-1);
       
       // 指针 curr 指向新链表虚拟节点 h，用于进行循环
       ListNode* curr = h;

       // 指针 p1 指向 l1 头节点
       ListNode* p1 = l1;

       // 指针 p1 指向 l2 头节点
       ListNode* p2 = l2;

       
       // C++11 新标准中引入了 nullptr 来声明一个“空指针”,新标准建议使用 nullptr 代替 NULL 来声明空指针。
       // 这里的意思是，当指针 p1 和 p2 指向不为空的时候，执行循环
       while (p1 != nullptr && p2 != nullptr)
       {
           // 如果 p1 指向节点的值 <= p2 指向节点的值
           if (p1->val <= p2->val)
           {
               // 指针 curr 指向 指针p1 所指向的节点，因为 p1 所指向的节点的值较小
               curr->next = p1;

               // 指针 p1 指向单链表中的下一个节点
               p1 = p1->next;
           }
           // 如果 p1 指向节点的值 > p2 指向节点的值
           else
           {
               // curr 指向值较小的那个节点
               curr->next = p2;

               // 在 l2 上继续遍历链表，并进入下一次循环进行比较
               p2 = p2->next;
           }

           // curr 指针移动到 curr->next 所指向的节点
           curr = curr->next;

       }// 以此类推，直到 p1 或者 p2 指针移动到链表的末端



       // 当 l1 和 l2 两个之中有一个到了尾部，那么循环结束
       // 循环结束之后，需要判断到底哪一个链表先到链表的末端


       // 如果是 l2 先到了链表末端，那么 p1 != nullptr
       // 所以 curr->next 指向 p1 
       // p1 后续节点已经排好序了，故直接合并进来就好
       if (p1 != nullptr)
       {
           curr->next = p1;
       }

       // 如果是 l1 先到了链表末端，那么 p2 != nullptr
       // 所以 curr->next 指向 p2 
       // p2 后续节点已经排好序了，故直接合并进来就好
       if (p2 != nullptr)
       {
           curr->next = p2;
       }

       // 新建一个链表节点 retNode ，将虚拟节点指向的下一个节点（即新链表的头节点）
       ListNode* retNode = h->next;

       // 删除所设置的虚拟头节点
       delete h;

       // 返回合并后的新链表，此时已经没有的虚拟节点。
       return retNode;
   }
};

今天便开始踏上算法刷题之旅了，在此先立个 Flag，希望自己能够坚持到明年拿到理想 Offer 的那一天！