兰州 网站建设,网页制作基础及html,徐州seo公司,深圳网站建设的公司招聘目录
从尾到头打印链表_牛客题霸_牛客网
160. 相交链表 141. 环形链表 142. 环形链表 II
138. 复制带随机指针的链表 从尾到头打印链表_牛客题霸_牛客网 输入一个链表的头节点#xff0c;按链表从尾到头的顺序返回每个节点的值#xff08;用数组返回#xff09;。 如输入…目录
从尾到头打印链表_牛客题霸_牛客网
160. 相交链表 141. 环形链表 142. 环形链表 II
138. 复制带随机指针的链表 从尾到头打印链表_牛客题霸_牛客网 输入一个链表的头节点按链表从尾到头的顺序返回每个节点的值用数组返回。 如输入{1,2,3}的链表如下图: 返回一个数组为[3,2,1] 0 链表长度 10000 【解法一】没学过c时 反转计数创建数组
* struct ListNode {* int val;* struct ListNode *next;* };*/int* printListFromTailToHead(struct ListNode* listNode, int* returnSize ) {// write code here// 反转链表if(NULL listNode)return NULL;struct ListNode* cur listNode;struct ListNode* next listNode;struct ListNode* prev NULL;int count 0;while(cur){count;next cur-next;cur-next prev;prev cur;cur next;}// 计数存入数组int *temp (int *)malloc(sizeof(int)*count);for(int i 0; i count; i){temp[i] prev-val;prev prev-next;}*returnSize count;return temp;
}
【解法二】 遍历一遍 放入vector进行反转
class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {vectorint res;if(headnullptr)return res;ListNode* cur head;while(cur){res.push_back(cur-val);cur cur-next;}reverse(res.begin(), res.end());return res;}
};【解法三】DFS
class Solution {
public:vectorint res;void DFS(ListNode* cur){if(cur){DFS(cur-next);res.push_back(cur-val);}}vectorint printListFromTailToHead(ListNode* head) {DFS(head);return res;}
};【解法四】一次遍历入栈之后把元素出栈入数组
class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {vectorint res;stackint s;while(head){s.push(head-val);headhead-next;}while(!s.empty()){res.push_back(s.top());s.pop();}return res;}
};160. 相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 自定义评测 评测系统 的输入如下你设计的程序 不适用 此输入 intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中从头节点开始跳到交叉节点的节点数 skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 来源力扣LeetCode 链接https://leetcode.cn/problems/intersection-of-two-linked-lists 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headAnullptr || headBnullptr)return nullptr;ListNode *l1 headA, *l2 headB;while(l1 ! l2){l1 l1nullptr ? headB : l1-next;l2 l2nullptr ? headA : l2-next;}return l1;}
}; 141. 环形链表 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 示例 1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。 class Solution {
public:bool hasCycle(ListNode *head) {//if(headnullptr || head-nextnullptr)return false;ListNode* fast head;ListNode* slow head;while(fast!nullptr fast-next!nullptr){fast fast-next-next;slow slow-next;if(fast slow) // 如果快慢指针相遇 则有环return true;}return false;}
}; 142. 环形链表 II 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。 class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast head;ListNode *slow head;bool flag 0;while(fast!nullptr fast-next!nullptr){fast fast-next-next;slow slow-next;if(slow fast){flag 1; // 找到第一个相遇结点break;}}if(flag0)return nullptr;ListNode *cur head; // 从head开始一起往后走while(cur ! fast) {cur cur-next; //再次相遇即为入环口fast fast-next;}return cur;}
}; 138. 复制带随机指针的链表 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示 val一个表示 Node.val 的整数。 random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。 示例 1 【解法一】使用哈希表来存储旧结点与新结点之间的对印关系
class Solution {
public:Node* copyRandomList(Node* head) {if(head nullptr) return nullptr;Node* newhead new Node(0);newhead-next nullptr;Node* cur head, *pre newhead;mapNode*, Node* mp;while(cur){Node* node new Node(cur-val);pre-next node;mp[cur] node;cur cur-next;pre pre-next;}for(auto node : mp){if(node.first-random nullptr)node.second-random nullptr;elsenode.second-random mp[node.first-random];}return newhead-next;}
};
【解法二】
/*
// 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 nullptr;Node* cur head;while(cur){Node* node new Node(cur-val);node-next cur-next;cur-next node;cur node-next;}for(cur head; cur ! nullptr; curcur-next-next){if(cur-random nullptr)cur-next-random nullptr;elsecur-next-random cur-random-next;}cur head-next;Node *pre head, *newhead head-next;while(cur-next){pre-next pre-next-next;cur-next cur-next-next;pre pre-next;cur cur-next;}pre-next nullptr;return newhead;}
};
