l2-022 重排链表 (25 分)
时间: 2023-04-20 12:01:56 浏览: 87
题目描述
给定一个链表,将其重新排列后按照原来的顺序输出。
输入格式
第一行包含一个整数 N,表示链表的长度。
第二行包含 N 个整数,表示链表中的结点编号。
第三行包含 N 个整数,表示链表中每个结点的值。
第四行包含 N 个整数,表示链表中每个结点的下一个结点编号,-1 表示链表的结尾。
输出格式
按照原来的顺序输出重新排列后的链表。
输入样例
5
4 2 5 1 3
-1 4 2 5 1
3 1 2 4 -1
输出样例
1 5 3 2 4
算法1
(链表操作) $O(n)$
1.将链表中的元素存入数组中
2.将数组排序
3.将数组中的元素重新连接成链表
时间复杂度
参考文献
python3 代码
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
算法3
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
相关问题
L2-022 重排链表
根据题目要求,我们需要将给定的单链表重新排列为Ln→L1→Ln−1→L2→⋯的形式。可以使用两个数组来实现这个目标。首先,我们可以遍历链表,将链表中的每个节点的地址按顺序存储到一个数组中。接下来,我们可以利用这个数组来构建我们需要的排列后的链表。具体步骤如下:
1. 定义一个结构体,用于存储链表节点的数值和下一个节点的地址。
2. 遍历链表,将每个节点的地址按顺序存储到一个数组中。
3. 定义一个新的数组,利用第一个数组中的节点地址来构建排列后的链表。具体方法是,按照Ln→L1→Ln−1→L2→⋯的顺序,依次将第一个数组中的节点地址赋值给新数组中的每个元素。
4. 按照排列后的链表顺序,依次输出新数组中的节点数值即可。
总结一下,我们可以按照上述方法实现题目要求的重排链表的功能。引用提供了一个类似的思路,可以作为参考。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [L2-022 重排链表 【STL】](https://blog.csdn.net/wangws_sb/article/details/88644986)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [L2-022 重排链表](https://blog.csdn.net/weixin_45897672/article/details/104703349)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
l2-002 链表去重 (25 分)
### 回答1:
在单链表中,如何去除重复的元素?
方法1:
1. 创建一个空的哈希表
2. 遍历链表,对于每个遍历到的节点,将其值放入哈希表中
3. 如果哈希表中已经存在该值,则删除该节点
方法2:
1. 从头节点开始,遍历整个链表
2. 对于每个遍历到的节点,从该节点的下一个节点开始,查找与该节点值相同的节点
3. 如果找到相同节点,则删除该节点
注意,这两种方法都需要维护链表的头节点。
### 回答2:
题目描述
给定一个带有重复元素的单链表,删除链表中重复的元素,使得链表中所有元素都是唯一的。
注意:不保留原链表中重复出现的数字。
输入格式:
第一行一个整数 N,为链表的总节点数。即下面的链表中,的数量。
第二行为不超过 N 的正整数,是单链表的节点的值。
输出格式:
链表的输出格式为
N node1→node2→node3→...nodeN
其中N为链表中节点个数,nodei表示链表中第i个节点的值。
注意:
如果链表为空,输出 NULL 。
如果链表有多个头结点,请保留最后一个。例如,链表1→2→2→3→3→4,应该输出1→4。
样例输入:
5
1 2 2 3 4
样例输出:
4 1→2→3→4
解题思路
本题需要对一个链表进行去重操作,使得链表中的每个元素只出现一次。根据这个描述,我们可以思考一下如何进行去重操作。
首先,我们可以开一个 hash 表,记录每个出现过的元素。然后对于链表中的每个元素,我们都查看一下它是否已经出现过,如果已经出现过,那么我们就将其删掉。
需要注意的是,如果链表有多个头结点,我们应该只保留最后一个头结点。那么,我们就需要在找出所有重复元素的位置之后,再去掉多余的头结点。
需要注意的一点是,这里题中的链表是单链表,而不是双向链表。这意味着我们不能通过双向指针来删除节点。 因此,我们只能遍历链表来找出重复元素的位置,并将它们删除。
时间复杂度:极端情况下,所有元素都不相同,那么 hash 表中就会存储所有元素,时间复杂度为 $O(n)$。在 worst case 时,遍历所有元素取出重复元素,时间复杂度为 $O(n)$。综合起来,时间复杂度为 $O(n)$。空间复杂度为 $O(n)$。
### 回答3:
思路:
题目要求实现链表去重,那么我们可以使用哈希表来实现。具体思路如下:
1. 定义一个哈希表,记录链表中每个值出现的次数。
2. 遍历链表,如果当前节点值在哈希表中的值已经是1了,说明已经出现过了,那么将当前节点从链表中删除。
3. 如果当前节点值在哈希表中的值还不是1,说明还没有出现过,那么将当前节点的值在哈希表中的值标记为1。
4. 继续遍历链表,直到到达链表的末尾为止。
5. 返回处理好的链表。
代码实现如下:
```cpp
#include <iostream>
#include <unordered_map>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return nullptr;
unordered_map<int, int> map;
ListNode* cur = head;
while (cur) {
map[cur->val]++;
cur = cur->next;
}
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
cur = head;
while (cur) {
if (map[cur->val] > 1) {
pre->next = cur->next;
cur = cur->next;
} else {
pre = cur;
cur = cur->next;
}
}
return dummy->next;
}
int main() {
// Test case: 1 -> 2 -> 2 -> 3 -> 3 -> 4
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(3);
head->next->next->next->next = new ListNode(3);
head->next->next->next->next->next = new ListNode(4);
ListNode* result = deleteDuplicates(head);
while (result) {
cout << result->val << "->";
result = result->next;
}
cout << "NULL" << endl;
return 0;
}
```
复杂度分析:
时间复杂度:我们需要遍历整个链表来构建哈希表,时间复杂度为 O(n),同时我们需要再次遍历链表来删除重复节点,时间复杂度为 O(n),因此总的时间复杂度为 O(n)。
空间复杂度:我们需要一个哈希表来存储链表中每个节点的值,因此空间复杂度为 O(n)。