[2020.10.14] 实现两个单向有序链表的合并

递归方法

重做了一遍

• 递归相对直观
• 处理行输入用了stringstream，处理多余的空格，十分方便
• 简化链表

后面迭代法可能有些说法错误，有部分多余，不过以下代码比较简单了。理解如何实现就行。

#include <iostream>
#include <string>
#include <sstream>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::getline;
using std::stringstream;
using std::to_string;

// 链表
struct LinkedList {
  int value;
  LinkedList *next;

  LinkedList(int x): value(x), next(nullptr){}
};

void list_init(LinkedList *list, string s) {
  auto tmp = list;
  int x{0};
  stringstream ss(s);
  while (ss >> x) {
    tmp->next = new LinkedList(x);
    tmp = tmp->next;
  }
}

void list_print(const LinkedList *list) {
  string res{};
  auto tmp = list;
  while (tmp != nullptr) {
    res += to_string(tmp->value);
    if (tmp->next != nullptr) {
      res += " ";
    }
    tmp = tmp->next;
  }
  cout << res << endl;
}

LinkedList* merge(LinkedList *list1, LinkedList *list2) {
  if (list1 == nullptr) return list2;
  if (list2 == nullptr) return list1;

  if (list1->value < list2->value) {
    list1->next = merge(list1->next, list2);
    return list1;
  } else {
    list2->next = merge(list1, list2->next);
    return list2;
  }
}

int main(int argc, char **argv) {
  auto *list1 = new LinkedList(0);
  auto *list2 = new LinkedList(0);
  auto tmp = list1;

  string s;
  // get 数据
  getline(cin, s);
  list_init(list1, s);
  getline(cin, s);
  list_init(list2, s);

  auto res = merge(list1->next, list2->next);

  list_print(res);

  return 0;
}

初次做失误 -- 迭代方法可用

尝试用使用类，统一封装方法，这个代码有不少问题还是有很多问题：

• 无法优雅处理链表的录入，违规输入没有报错机制；
• 对空表直接判断，此处加了一个标志；
• 写了节点相关的方法，但是create_node和append_node可以合并；
• merge的处理仅仅考虑的数据，直接创建了新的链表使用，这个和就和作弊法差不多了。
• 等等等

虽然很想完美处理，搞个通用的，太费时间了，能够解决问题就行；

核心代码：

下面展开给独立函数也是可以用的。

看了下题解，想法差不多；

  /**
连接有序节点
题目关键

遵守链表规则，修改next指向

有疑问，此处的链表可以为空吗
*/
  void sort_merge_list(LinkedList *linked_list) {
    // 处理空表
    if (this->is_empty && !linked_list->is_empty) {
      this->m_value = linked_list->m_value;
      this->next = linked_list->next;
      this->is_empty = false;

      return;
    }

    if (linked_list->is_empty) {
      return;
    }

    auto it = this;
    auto the = linked_list;

    auto *res = new LinkedList();

    // 标志
    bool has_node{false};
    int it_num{0}, the_num{0};
    // 比较
    while (it != nullptr || the != nullptr) {
      // 中转数字，用来记录大小的数字
      int tmp;
      it_num = it != nullptr ? it->m_value : it_num;
      the_num = the != nullptr ? the->m_value : the_num;

      // 判断
      // 此处到最后一个数字需要特殊处理，否则无法跳出循环
      if (it_num < the_num) {
    tmp = it_num;

    // 最终一个数字问题
    // 其中一个为nullptr的情况则进行置换
    if (it == nullptr && the != nullptr) {
      tmp = the_num;
      the = the->next;
    }
    it = it != nullptr ? it->next : it;
      } else {
    tmp = the_num;

    if (the == nullptr && it != nullptr) {
      tmp = it_num;
      it = it->next;
    }
    the = the != nullptr ? the->next : the;
      }

      // 加入内容
      if (!has_node) {
    res->create_node(tmp);
    has_node = true;
      } else {
    res->append_node(tmp);
      }
    }

    // 仅仅确保了数值相等
    // 头节点的地址发生了变化
    // 类创建链表 解决这个问题 有些麻烦
    this->m_value = res->m_value;
    this->next = res->next;
  }
};

完整代码：

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::getline;
using std::stoi;
using std::to_string;

// 无头节点
class LinkedList{
private:
  int m_value{0};
public:
  bool is_empty{true};

public:
  LinkedList *next{nullptr};

public:
  LinkedList() {};
  LinkedList(int value) {
    // 正常初始化
    this->create_node(value);

  }
  // 批量创建
  LinkedList(string values) {
    this->create_nodes(values);
  }

  ~LinkedList() {}

protected:
  /**
批量添加节点
string values 直接获取一行数据

TODO: 处理仅空格情况或者无输入
   */
  void create_nodes(string values) {
    // 转换字符串 手动
    string num_str{};
    int count{0};
    for (auto c : values) {
      if (isdigit(c)) {
    num_str += c;
      }
      if (isspace(c)) {
    int num = stoi(num_str);
    if (count++ != 0) {
      this->append_node(num);
    } else {
      this->create_node(num);
    }
    num_str = "";
      }
    }

    // 还有一个元素需要添加
    if (num_str == "") {
      return;
    }
    int num = stoi(num_str);
    if (count != 0) {
      this->append_node(num);
    } else {
      // 一个元素的情况
      this->create_node(num);
    }
  }

  /**
创建节点
*/
  void create_node(int value) {
    this->m_value = value;
    this->next = nullptr;
    this->is_empty = false;
  }

  /**
向后添加节点

该方法没有很好的处理错误，不暴露出去
*/
  void append_node(int value) {
    if (this->next == nullptr) {
      auto *new_node = new LinkedList(value);
      this->next = new_node;
    } else {
      this->next->append_node(value);
    }
  }

public:
  /**
打印节点
*/
  void print_nodes() {
    auto tmp = this;
    string res{};
    while (tmp->next != nullptr) {
      res += to_string(tmp->m_value);
      res += " ";
      // cout << tmp->m_value;
      tmp = tmp->next;
    }
    res += to_string(tmp->m_value);
    cout << res << endl;
  }

  /**
连接有序节点
题目关键

遵守链表规则，修改next指向

有疑问，此处的链表可以为空吗
*/
  void sort_merge_list(LinkedList *linked_list) {
    // 处理空表
    if (this->is_empty && !linked_list->is_empty) {
      this->m_value = linked_list->m_value;
      this->next = linked_list->next;
      this->is_empty = false;

      return;
    }

    if (linked_list->is_empty) {
      return;
    }

    auto it = this;
    auto the = linked_list;

    auto *res = new LinkedList();

    // 标志
    bool has_node{false};
    int it_num{0}, the_num{0};
    // 比较
    while (it != nullptr || the != nullptr) {
      // 中转数字，用来记录大小的数字
      int tmp;
      it_num = it != nullptr ? it->m_value : it_num;
      the_num = the != nullptr ? the->m_value : the_num;

      // 判断
      // 此处到最后一个数字需要特殊处理，否则无法跳出循环
      if (it_num < the_num) {
    tmp = it_num;

    // 最终一个数字问题
    // 其中一个为nullptr的情况则进行置换
    if (it == nullptr && the != nullptr) {
      tmp = the_num;
      the = the->next;
    }
    it = it != nullptr ? it->next : it;
      } else {
    tmp = the_num;

    if (the == nullptr && it != nullptr) {
      tmp = it_num;
      it = it->next;
    }
    the = the != nullptr ? the->next : the;
      }

      // 加入内容
      if (!has_node) {
    res->create_node(tmp);
    has_node = true;
      } else {
    res->append_node(tmp);
      }
    }

    // 仅仅确保了数值相等
    // 头节点的地址发生了变化
    // 类创建链表 解决这个问题 有些麻烦
    this->m_value = res->m_value;
    this->next = res->next;
  }
};

int main(int argc, char** argv)
{
  string list1{}, list2{};

  // cout << "链表1" << endl;
  getline(cin, list1);
  // cout << "链表2" << endl;
  getline(cin, list2);

  auto *linked_list1 = new LinkedList(list1);
  auto *linked_list2 = new LinkedList(list2);

  // linked_list1->print_nodes();
  // linked_list2->print_nodes();

  linked_list1->sort_merge_list(linked_list2);
  linked_list1->print_nodes();

  return 0;
}