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、付费专栏及课程。