本文主要是介绍每日两题 / 138. 随机链表的复制 148. 排序链表(LeetCode热题100),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
138. 随机链表的复制 - 力扣(LeetCode)
用哈希表记录原链表中的节点是否被复制过
遍历原链表并通过哈希表维护新链表
/*
// 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:Node* copyRandomList(Node* head) {if (head == nullptr) return head;unordered_map<Node*, Node*> mp;Node *new_head = new Node(head->val);mp[head] = new_head;Node *cur = head, *new_cur = new_head;while (cur){auto &next = mp[cur->next];auto &random = mp[cur->random];if (next == nullptr && cur->next) next = new Node(cur->next->val);if (random == nullptr && cur->random) random = new Node(cur->random->val);new_cur->next = next, new_cur->random = random;cur = cur->next;new_cur = new_cur->next;}return new_head;}
};
148. 排序链表 - 力扣(LeetCode)
将链表转换成数组,sort后再转换成链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {vector<int> a;ListNode *cur = head;while (cur){a.push_back(cur->val);cur = cur->next;}sort(a.begin(), a.end());ListNode *new_head = new ListNode;cur = new_head;for (auto t : a){cur->next = new ListNode(t);cur = cur->next;}return new_head->next;}
};
这篇关于每日两题 / 138. 随机链表的复制 148. 排序链表(LeetCode热题100)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!