目 录CONTENT

文章目录

反转链表

TalentQ
2025-09-11 / 0 评论 / 0 点赞 / 1 阅读 / 0 字

1 简单实现

#include <memory>
#include <iostream>

struct Node {
  int data;
  std::unique_ptr<Node> next;
  Node(int value) : data(value), next(nullptr) {}
};

std::unique_ptr<Node> reverse(std::unique_ptr<Node> head) {

  std::unique_ptr<Node> pre = nullptr;
  std::unique_ptr<Node> cur = std::move(head);
  std::unique_ptr<Node> next = nullptr;

  while (cur != nullptr)
  {
    next = std::move(cur->next);
    cur->next = std::move(pre);
    pre = std::move(cur);
    cur = std::move(next);
  }

  return pre;
}

void PrintList(std::unique_ptr<Node>& head) {
  Node* cur = head.get();
  while (cur) {
    std::cout << cur->data << " ";
    cur = cur->next.get();
  }
}

int main() {
  // 非常不优雅,我能写一天
  std::unique_ptr<Node> head = std::make_unique<Node>(1);
  head->next = std::make_unique<Node>(2);
  head->next->next = std::make_unique<Node>(3);
  head->next->next->next = std::make_unique<Node>(4);

  PrintList(head);
  std::cout << std::endl;

  head = reverse(std::move(head));

  PrintList(head);
  std::cout << std::endl;

  return 0;
}

2 优雅实现

#include <iostream>
#include <memory>

class LinkList {
 public:
  LinkList() = default;
  LinkList(const LinkList&) = delete;
  LinkList& operator=(const LinkList&) = delete;
  LinkList(LinkList&&) = default;
  LinkList& operator=(LinkList&&) = default;

  void reverse() {
    std::unique_ptr<Node> pre = nullptr;
    std::unique_ptr<Node> cur = std::move(head_);
    std::unique_ptr<Node> next = nullptr;
    while (cur) {
      next = std::move(cur->next);
      cur->next = std::move(pre);
      pre = std::move(cur);
      cur = std::move(next);
    }

    head_ = std::move(pre);
  }

  void append(int value) {
    std::unique_ptr<Node> new_node = std::make_unique<Node>(value);
    if (head_ == nullptr) {
      head_ = std::move(new_node);
      return;
    }

    Node* cur = head_.get();
    while(cur->next) {
      cur = cur->next.get();
    }

    cur->next = std::move(new_node);
  }

  void print() {
    if (head_ == nullptr) return;

    Node* cur = head_.get();
    while (cur) {
      std::cout << cur->data << " ";
      cur = cur->next.get();
    }
    std::cout << std::endl;
  }

 private:
  struct Node {
    int data;
    std::unique_ptr<Node> next;
    Node(int value) : data(value), next(nullptr) {}
  };

 std::unique_ptr<Node> head_;
};

int main() {
  LinkList list;
  int n, tmp;
  
  std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::cin >> tmp;
    list.append(tmp);
  }

  list.print();
  list.reverse();
  list.print();
  
  return 0;
}

0

评论区