链表OJ（一）

目录

从尾到头打印链表_牛客题霸_牛客网

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:vector<int> printListFromTailToHead(ListNode* head) {vector<int> res;if(head==nullptr)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:vector<int> res;void DFS(ListNode* cur){if(cur){DFS(cur->next);res.push_back(cur->val);}}vector<int> printListFromTailToHead(ListNode* head) {DFS(head);return res;}
};

【解法四】一次遍历入栈，之后把元素出栈入数组

class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {vector<int> res;stack<int> s;while(head){s.push(head->val);head=head->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(headA==nullptr || headB==nullptr)return nullptr;ListNode *l1 = headA, *l2 = headB;while(l1 != l2){l1 = l1==nullptr ? headB : l1->next;l2 = l2==nullptr ? 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(head==nullptr || head->next==nullptr)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(flag==0)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;map<Node*, 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; cur=cur->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;}
};