text: # 【剑指Offer】链表
  
  36 篇文章 0 订阅
  
  ## 从尾到头打印链表
  
  输入：head = [1,3,2]
  
  
  
  0 <= 链表长度 <= 10000
  
  /**
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
  class Solution {
  public:
  }
  vector<int> ans;
  return ans;
  }
  };
  
  
  ps：这题其实要容易有很多解法，比如直接存数组然后反转还有直接用栈，题目太简单了，所以不详细说。
  
  ## 反转链表
  
  输入: 1->2->3->4->5->NULL
  
  
  
  0 <= 节点个数 <= 5000
  
  ### 解法一：
  
  /**
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
  class Solution {
  public:
  return h;
  }
  }
  };
  
  
  ### 解法二：
  
  /**
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
  class Solution {
  public:
  ListNode *pre = nullptr, *p = head;
  while(p){
  ListNode *tmp = p->next;
  p->next = pre;
  pre = p;
  if(tmp != nullptr){
  p = tmp;
  }else{
  return p;
  }
  }
  return nullptr;
  }
  };
  
  
  ## 复杂链表的复制
  
  输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
  
  
  
  输入：head = [[1,1],[2,1]]
  
  
  
  输入：head = [[3,null],[3,0],[3,null]]
  
  
  
  输入：head = []
  
  
  
  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000
  
  ### 解法一：
  
  /*
  // Definition for a Node.
  class Node {
  public:
  int val;
  Node* next;
  Node* random;
  
  Node(int _val) {
  val = _val;
  next = NULL;
  random = NULL;
  }
  };
  */
  class Solution {
  public:
  map<Node*, Node*> mp;
  while(p){
  Node * nn = new Node(p->val);
  mp[p] = nn;
  nn->next = p->next;
  nn->random = p->random;
  p1->next = nn;
  p = p->next;
  p1 = p1->next;
  }
  p = head, p1 = ans;
  while(p1){
  if(p1->random != nullptr)p1->random = mp[p1->random];
  p = p->next;
  p1 = p1->next;
  }
  return ans;
  }
  };
  
  
  ### 解法二：
  
  /*
  // Definition for a Node.
  class Node {
  public:
  int val;
  Node* next;
  Node* random;
  
  Node(int _val) {
  val = _val;
  next = NULL;
  random = NULL;
  }
  };
  */
  class Solution {
  public:
  while(p){
  Node *nn = new Node(p->val);
  nn->next = p->next;
  p->next = nn;
  p = nn->next;
  }
  while(p){
  if(p->random != nullptr)p->next->random = p->random->next;
  else p->next->random = nullptr;
  p = p->next->next;
  }
  while(p){
  Node* tmp = p->next;
  p->next = p->next->next;
  p = p->next;
  if(tmp->next != nullptr)tmp->next = tmp->next->next;
  }
  
  return ans;
  }
  };
  
  
  ## 最后
  
  【剑指Offer】系列：
  【剑指Offer】栈
  
  • 1
  点赞
  • 1
  收藏
  觉得还不错? 一键收藏
  • 0
  评论
  08-14 117
  08-19 334
  08-20 175
  10-23 326
  08-23 423
  07-08 253
  11-26 126
  04-25 131
  05-19 227
  
  ### “相关推荐”对你有帮助么？
  
  • 非常没帮助
  • 没帮助
  • 一般
  • 有帮助
  • 非常有帮助
  
  1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
  2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。
explanation: The provided text is a collection of code snippets and problem descriptions related to linked list operations in C++. It includes problems such as printing a linked list in reverse, reversing a linked list, and copying a complex linked list. Each problem is accompanied by one or more solution implementations.
  
  The text does not contain any explicit math questions or answers. It primarily focuses on algorithmic and data structure problems.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 【剑指Offer】链表
  
  36 篇文章 0 订阅
  
  ## 从尾到头打印链表
  
  输入：head = [1,3,2]
  
  
  
  0 <= 链表长度 <= 10000
  
  /**
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
  class Solution {
  public:
  }
  vector<int> ans;
  return ans;
  }
  };
  
  
  ps：这题其实要容易有很多解法，比如直接存数组然后反转还有直接用栈，题目太简单了，所以不详细说。
  
  ## 反转链表
  
  输入: 1->2->3->4->5->NULL
  
  
  
  0 <= 节点个数 <= 5000
  
  ### 解法一：
  
  /**
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
  class Solution {
  public:
  return h;
  }
  }
  };
  
  
  ### 解法二：
  
  /**
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
  class Solution {
  public:
  ListNode *pre = nullptr, *p = head;
  while(p){
  ListNode *tmp = p->next;
  p->next = pre;
  pre = p;
  if(tmp != nullptr){
  p = tmp;
  }else{
  return p;
  }
  }
  return nullptr;
  }
  };
  
  
  ## 复杂链表的复制
  
  输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
  
  
  
  输入：head = [[1,1],[2,1]]
  
  
  
  输入：head = [[3,null],[3,0],[3,null]]
  
  
  
  输入：head = []
  
  
  
  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000
  
  ### 解法一：
  
  /*
  // Definition for a Node.
  class Node {
  public:
  int val;
  Node* next;
  Node* random;
  
  Node(int _val) {
  val = _val;
  next = NULL;
  random = NULL;
  }
  };
  */
  class Solution {
  public:
  map<Node*, Node*> mp;
  while(p){
  Node * nn = new Node(p->val);
  mp[p] = nn;
  nn->next = p->next;
  nn->random = p->random;
  p1->next = nn;
  p = p->next;
  p1 = p1->next;
  }
  p = head, p1 = ans;
  while(p1){
  if(p1->random != nullptr)p1->random = mp[p1->random];
  p = p->next;
  p1 = p1->next;
  }
  return ans;
  }
  };
  
  
  ### 解法二：
  
  /*
  // Definition for a Node.
  class Node {
  public:
  int val;
  Node* next;
  Node* random;
  
  Node(int _val) {
  val = _val;
  next = NULL;
  random = NULL;
  }
  };
  */
  class Solution {
  public:
  while(p){
  Node *nn = new Node(p->val);
  nn->next = p->next;
  p->next = nn;
  p = nn->next;
  }
  while(p){
  if(p->random != nullptr)p->next->random = p->random->next;
  else p->next->random = nullptr;
  p = p->next->next;
  }
  while(p){
  Node* tmp = p->next;
  p->next = p->next->next;
  p = p->next;
  if(tmp->next != nullptr)tmp->next = tmp->next->next;
  }
  
  return ans;
  }
  };
  
  
  ## 最后
  
  【剑指Offer】系列：
  【剑指Offer】栈
  
  • 1
  点赞
  • 1
  收藏
  觉得还不错? 一键收藏
  • 0
  评论
  08-14 117
  08-19 334
  08-20 175
  10-23 326
  08-23 423
  07-08 253
  11-26 126
  04-25 131
  05-19 227
  
  ### “相关推荐”对你有帮助么？
  
  • 非常没帮助
  • 没帮助
  • 一般
  • 有帮助
  • 非常有帮助
  
  1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
  2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text is a collection of code snippets and problem descriptions related to linked list operations in C++. It includes problems such as printing a linked list in reverse, reversing a linked list, and copying a complex linked list. Each problem is accompanied by one or more solution implementations.
  
  The text does not contain any explicit math questions or answers. It primarily focuses on algorithmic and data structure problems.
  
  Label: no-question