[連結清單]BM4-合并兩個排序的連結清單-簡單

描述

輸入兩個遞增的連結清單，單個連結清單的長度為n，合并這兩個連結清單并使新連結清單中的節點仍然是遞增排序的。

資料範圍： ，

要求：空間複雜度 ，時間複雜度 

如輸入{1,3,5},{2,4,6}時，合并後的連結清單為{1,2,3,4,5,6}，是以對應的輸出為{1,2,3,4,5,6}，轉換過程如下圖所示：

或輸入{-1,2,4},{1,3,4}時，合并後的連結清單為{-1,1,2,3,4,4}，是以對應的輸出為{-1,1,2,3,4,4}，轉換過程如下圖所示：

示例1

輸入：

{1,3,5},{2,4,6}      

傳回值：

{1,2,3,4,5,6}      

示例2

輸入：

{},{}      

複制傳回值：

{}      

示例3

輸入：

{-1,2,4},{1,3,4}      

{-1,1,2,3,4,4}      

題解

• 1. 确定頭節點，確定left->val <= right->val
• 2. 使用指針head指向left，讓left = left->next，并記錄tail節點作為新節點的末尾節點
• 3. 循環比較left->val和right->val，直到left和right都為空

• 如果left或者right為空，則直接取left或者right的下一個節點作為tail->next節點
• 如果left和right都不會空，則讓tail->next指向值較小的一個節點，并更新left或者right節點為其next

struct ListNode
{
  int val;
  struct ListNode *next;
  ListNode(int x) : val(x), next(nullptr)
  {
  }
};

class Solution
{
public:
  ListNode *Merge(ListNode *left, ListNode *right)
  {
    if (left == nullptr)
    {
      return right;
    }

    if (right == nullptr)
    {
      return left;
    }

    if (left->val > right->val)
    {
      return Merge(right, left);
    }

    ListNode *head = left;
    ListNode *tail_node = left;
    left = left->next;
    while (left != nullptr || right != nullptr)
    {
      if (left == nullptr)
      {
        tail_node->next = right;
        right = right->next;
        tail_node = tail_node->next;
      }
      else if (right == nullptr)
      {
        tail_node->next = left;
        left = left->next;
        tail_node = tail_node->next;
      }
      else
      {
        if (left->val < right->val)
        {
          auto next = left->next;
          tail_node->next = left;
          left = next;
          tail_node = tail_node->next;
        }
        else
        {
          auto next = right->next;
          tail_node->next = right;
          right = next;
          tail_node = tail_node->next;
        }
      }
    }

    return head;
  }
};