# 【剑指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、付费专栏及课程。
The provided text passage is a collection of code snippets and problem descriptions for several linked list manipulation problems in C++ from the "Sword to Offer" series. It does not contain any explicit mathematical questions or answers.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 【剑指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、付费专栏及课程。
user
The provided text passage is a collection of code snippets and problem descriptions for several linked list manipulation problems in C++ from the "Sword to Offer" series. It does not contain any explicit mathematical questions or answers.

TYPE: NO_QUESTION