1 题目

反转指定的区间

2 题解

两种方式：

1. 先找到 left 和 right，记录好前后的位置，反转区间，再链接好；

2. 先找到 left，在到达 right 之前，逐个反转，到达 right 后则程序结束；

这两种方式的时间复杂度都是 O(n)。第一种方式需要两次遍历，第二种方式只需要一次遍历。

2.1 方式一

注释写的很清楚，逻辑也非常简单，但是实现稍微有点麻烦。不推荐这个方案。

#include <iostream>

template <typename T>
class LinkList {
 public:
  LinkList() : head_(nullptr), tail_(nullptr) {}
  ~LinkList() {
    if (head_ == nullptr) return;

    Node* list = head_;
    while (list) {
      Node* node = list;
      list = list->next;
      delete node;
    }
    head_ = nullptr;
    tail_ = nullptr;
  }

  void reverse_list_between(int left, int right) {
    if (head_ == nullptr) return;

    Node dummy_node;
    dummy_node.next = head_;
    Node* pre = &dummy_node;

    for (int i = 1; i < left; ++i) {
      pre = pre->next;
    }
    Node* left_node = pre->next;
    Node* left_node_pre = pre;

    for (int i = left; i < right; ++i) {
      pre = pre->next;
    }
    Node* right_node = pre->next;
    Node* right_node_next = right_node->next;

    left_node_pre->next = nullptr;
    right_node->next = nullptr;

    reverse(left_node);

    left_node_pre->next = right_node;
    left_node->next = right_node_next;

    head_ = dummy_node.next;
  }

  void print() const {
    Node* list = head_;
    while (list) {
      std::cout << list->data << ' ';
      list = list->next;
    }
    std::cout << std::endl;
  }

  void insert(T value) {
    if (head_ == nullptr) {
      head_ = new Node(value);
      tail_ = head_;
    } else {
      tail_->next = new Node(value);
      tail_ = tail_->next;
    }
  }

 private:
  struct Node {
    T data;
    Node* next;
    Node() : next(nullptr) {}
    Node(T value) : data(value), next(nullptr) {}
  };
  Node* head_;
  Node* tail_;

  void reverse(Node* list) {
    if (list == nullptr) return;

    Node *pre = nullptr, *cur = list, *next = nullptr;
    while (cur) {
      next = cur->next;
      cur->next = pre;
      pre = cur;
      cur = next;
    }
  }
};

int main() {
  int n = 10;
  LinkList<int> list;

  for (int i = 1; i <= n; ++i) {
    list.insert(i);
  }
  list.print();

  list.reverse_list_between(2, 8);
  list.print();

  return 0;
}

2.2 方式二 - 推荐

先找到 左节点 和其前驱节点 pre，这个 pre 一旦找到就不动了，后续会不断更新其后继;

也就是后续的节点都会被逐个插入到 pre 的后面，直到区间的右边界。

#include <iostream>

template <typename T>
class LinkList {
 public:
  LinkList() : head_(nullptr), tail_(nullptr) {}

  ~LinkList() {
    Node* list = head_;
    while (list) {
      Node* node = list;
      list = list->next;
      delete node;
    }
    head_ = nullptr;
    tail_ = nullptr;
  }

  // reverse
  void reverse_list_between(int left, int right) {
    if (head_ == nullptr) return;

    // 神来之笔
    // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
    Node dummy_node;
    dummy_node.next = head_;
    Node *pre = &dummy_node, *cur = head_, *next = nullptr;

    // 找到左节点和其前驱节点 pre，注意这个 pre
    // 一旦找到就不更新了，后面会不断更新它的后继
    for (int i = 1; i < left; ++i) {
      pre = pre->next;
    }
    cur = pre->next;

    for (int i = left; i < right; ++i) {
      next = cur->next;
      cur->next = next->next;
      next->next = pre->next;
      pre->next = next;
    }

    while (cur->next) {
      cur = cur->next;
    }
    tail_ = cur;

    head_ = dummy_node.next;
  }

  // print
  void print() {
    Node* node = head_;
    while (node) {
      std::cout << node->data << ' ';
      node = node->next;
    }
    std::cout << std::endl;
  }

  // insert
  void insert(T value) {
    if (head_ == nullptr) {
      head_ = new Node(value);
      tail_ = head_;
    } else {
      tail_->next = new Node(value);
      tail_ = tail_->next;
    }
  }

 private:
  struct Node {
    T data;
    Node* next;
    Node() : next(nullptr) {}
    Node(T value) : data(value), next(nullptr) {}
  };
  Node* head_;
  Node* tail_;
};

int main() {
  int n = 10;
  LinkList<int> list;

  for (int i = 1; i <= n; ++i) {
    list.insert(i);
  }
  list.print();

  list.reverse_list_between(2, 8);
  list.print();

  return 0;
}