剑指offer（一）-链表

（一）找出链表的环的入口结点
JZ23 链表中环的入口结点
中等 通过率：36.78% 时间限制：1秒 空间限制：64M
知识点链表哈希双指针
描述
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000，1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
输入描述：
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例1
输入：
{1,2},{3,4,5}
返回值：
3
说明：
返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2
输入：
{1},{}
返回值：
“null”
说明：
没有环，返回对应编程语言的空结点，后台程序会打印"null"
示例3
输入：
{},{2}

返回值：
2
说明：
环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {if (pHead == NULL || pHead->next == NULL || pHead->next->next == NULL) {return NULL;}ListNode* slow = pHead->next;ListNode* fast = pHead->next->next;while (slow != fast) {slow = slow->next;if (fast == NULL || fast->next == NULL || fast->next->next == NULL) {return NULL;}fast = fast->next->next;}slow = pHead;while (slow != fast) {slow = slow->next;fast = fast->next;}return slow;}
};

（二）判断链表是否有环
leetcode 141
141. 环形链表
难度简单
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
通过次数391,460
提交次数769,105

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {
public:bool hasCycle(ListNode *head) {if (head == NULL || head->next == NULL || head->next->next == NULL) {return false;}ListNode* slow = head->next;ListNode* fast = head->next->next;while (slow != fast) {slow = slow->next;if (fast == NULL || fast->next == NULL || fast->next->next == NULL) {return false;}fast = fast->next->next;}return true;}

（一）重复的结点不保留
JZ76 删除链表中重复的结点
中等 通过率：22.07% 时间限制：1秒 空间限制：64M
知识点链表
描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

数据范围：链表长度满足 0≤n≤1000 ，链表中的值满足 1≤val≤1000

进阶：空间复杂度 O(n) ，时间复杂度 O(n)

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

示例1
输入：
{1,2,3,3,4,4,5}
返回值：
{1,2,5}
示例2
输入：
{1,1,1,8}
返回值：
{8}
自己答案：

方法：使用unordered_map<int, int> mm 和 创建头结点

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if (pHead == NULL) {return NULL;}std::unordered_map<int, int> m;ListNode* cur = pHead;while (cur != NULL) {m[cur->val]++;cur = cur->next;}ListNode* res = new ListNode(0);res->next = pHead;cur = res;while (cur->next != NULL) {if (m[cur->next->val] != 1) {cur->next = cur->next->next;} else {cur = cur->next;}}return res->next;}
};

（二）重复的结点保留一个
Leetcode 83
83. 删除排序链表中的重复元素
难度简单
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
通过次数271,350
提交次数504,656
请问您在哪类招聘中遇到此题？

/*** 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* deleteDuplicates(ListNode* head) {ListNode* cur = head;ListNode* nex = head;while(nex != NULL){nex = nex->next;if(nex == NULL) {return head;}if(cur->val == nex->val) {cur->next = nex->next;} else {cur = cur->next;} }return head;}
};

JZ18 删除链表的节点
简单 通过率：60.23% 时间限制：1秒 空间限制：256M
知识点链表
描述
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
1.此题对比原题有改动
2.题目保证链表中节点的值互不相同
3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

数据范围:
0<=链表节点值<=10000
0<=链表长度<=10000
示例1
输入：
{2,5,1,9},5
返回值：
{2,1,9}

说明：
给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 2 -> 1 -> 9
示例2
输入：
{2,5,1,9},1
返回值：
{2,5,9}

说明：
给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 2 -> 5 -> 9

方法：pcur 指向最后一个结点

/*** struct ListNode {*  int val;*  struct ListNode *next;*  ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param val int整型 * @return ListNode类*/ListNode* deleteNode(ListNode* head, int val) {// write code hereif (head == NULL) {return NULL;}//为了解决第一个节点被删除的问题，新增一个头节点ListNode* res = new ListNode(0);res->next = head;ListNode* cur = res;while (cur->next != NULL) {if (cur->next->val == val) {cur->next = cur->next->next;} else {cur = cur->next;}}return res->next;}
};

JZ35 复杂链表的复制
较难 通过率：23.47% 时间限制：1秒 空间限制：64M
知识点链表
描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例:
输入:{1,2,3,4,5,3,5,#,2,#}
输出:{1,2,3,4,5,3,5,#,2,#}
解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。
以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
后半部分，3，5，#，2，#分别的表示为
1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null
如下图:

示例1
输入：
{1,2,3,4,5,3,5,#,2,#}
返回值：
{1,2,3,4,5,3,5,#,2,#}

方法：复制节点放在下一个位置

/*
struct RandomListNode {int label;struct RandomListNode *next, *random;RandomListNode(int x) :label(x), next(NULL), random(NULL) {}
};
*/class Solution {public:RandomListNode* Clone(RandomListNode* pHead) {//空节点直接返回if (pHead == NULL)return pHead;//第一步：使用单指针遍历链表，对每个节点新建一个拷贝节点，并插入到该节点之后。//原始节点RandomListNode* cur = pHead;//遍历原始链表，开始复制while (cur != NULL) {//拷贝节点RandomListNode* clone = new RandomListNode(cur->label);//将拷贝节点插入到原始节点后面clone->next = cur->next;cur->next = clone;cur = clone->next;}//第二步：使用双指针遍历链表，两个指针每次都移动两步，//拷贝节点的随机指针 调整为 指向节点的下一个节点。//原始节点  cur = pHead;//拷贝节点RandomListNode* clone = pHead->next;//返回结果RandomListNode* res = pHead->next;//连接新链表的random节点while (cur != NULL) {//跟随前一个连接randomif (cur->random == NULL)clone->random = NULL;else//后一个节点才是拷贝的clone->random = cur->random->next;//cur->next必定不为空cur = cur->next->next;//检查末尾节点if (clone->next != NULL)clone = clone->next->next;}//第三步：使用双指针再次遍历链表，两个指针每次都移动一步，//原始节点和拷贝节点的next指针 都调整为 指向节点的下一个节点。cur = pHead;clone = pHead->next;while (cur != NULL) {cur->next = cur->next->next;//检查末尾节点if (clone->next != NULL) {clone->next = clone->next->next;}cur = cur->next;clone = clone->next;}return res;}
};

JZ25 合并两个排序的链表
描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例1
输入：
{1,3,5},{2,4,6}
返回值：
{1,2,3,4,5,6}
示例2
输入：
{},{}
返回值：
{}
示例3
输入：
{-1,2,4},{1,3,4}
返回值：
{-1,1,2,3,4,4}

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if (pHead1 == NULL && pHead2 == NULL) {return NULL;}if (pHead1 == NULL && pHead2 != NULL) {return pHead2;}if (pHead1 != NULL && pHead2 == NULL) {return pHead1;}if (pHead1->val < pHead2->val) {pHead1->next = Merge(pHead1->next, pHead2);return pHead1;} else {pHead2->next = Merge(pHead1, pHead2->next);return pHead2;}}
};

JZ52 两个链表的第一个公共结点
简单 通过率：38.04% 时间限制：1秒 空间限制：64M
知识点链表
描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例1
输入：
{1,2,3},{4,5},{6,7}
返回值：
{6,7}
说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2
输入：
{1},{2,3},{}
返回值：
{}
说明：
2个链表没有公共节点 ,返回null，后台打印{}

方法：交叉遍历法

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {ListNode* head1 = pHead1;ListNode* head2 = pHead2;while (head1 != head2) {head1 = (head1 == NULL ? pHead2 : head1->next);head2 = (head2 == NULL ? pHead1 : head2->next);}return head1;}
};

JZ22 链表中倒数最后k个结点
简单 通过率：39.15% 时间限制：1秒 空间限制：256M
知识点链表
描述
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤105，0≤ai​≤109，0≤k≤109
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
示例1
输入：
{1,2,3,4,5},2
返回值：
{4,5}
说明：
返回倒数第2个节点4，系统会打印后面所有的节点来比较。
示例2
输入：
{2},8
返回值：
{}

方法：head指针使用for循环，head指针 走到 最后一个节点

/*** struct ListNode {*  int val;*  struct ListNode *next;*  ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead ListNode类 * @param k int整型 * @return ListNode类*/ListNode* FindKthToTail(ListNode* pHead, int k) {// write code hereif (pHead == NULL || k <= 0) {return NULL;}ListNode* head = pHead;ListNode* tail = pHead;for (int i = 0; i < k-1; ++i) {if (head->next != NULL) {head = head->next;} else {return NULL;}}while (head->next != NULL) {head = head->next;tail = tail->next;}return tail;}
};

JZ6 从尾到头打印链表
简单 通过率：28.84% 时间限制：1秒 空间限制：64M
知识点链表
描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000
示例1
输入：
{1,2,3}
返回值：
[3,2,1]
示例2
输入：
{67,0,24,58}
返回值：
[58,24,0,67]
自己答案：

方法：栈

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:vector<int> printListFromTailToHead(ListNode* head) {std::vector<int> vec;if (head == NULL) {return vec;}std::stack<int> sta;while (head != NULL) {sta.push(head->val);head = head->next;}while (!sta.empty()) {vec.push_back(sta.top());sta.pop();}return vec;}
};

JZ24 反转链表
简单 通过率：38.82% 时间限制：1秒 空间限制：64M
知识点链表
描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：

示例1
输入：
{1,2,3}
返回值：
{3,2,1}
示例2
输入：
{}
返回值：
{}
说明：
空链表则输出空

第一个方法：栈

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {if (pHead == NULL) {return NULL;}std::stack<ListNode*> sta;while (pHead != NULL) {sta.push(pHead);pHead = pHead->next;}ListNode* res = sta.top();ListNode* cur = sta.top();sta.pop();while (!sta.empty()) {cur->next = sta.top();sta.pop();cur = cur->next;}cur->next = NULL;return res;}
};

第二个方法：数组

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/class Solution {
public:ListNode* ReverseList(ListNode* pHead) {if (pHead == NULL) {return NULL;}std::vector<ListNode*> vec;while (pHead != NULL) {vec.push_back(pHead);pHead = pHead->next;}reverse(vec.begin(), vec.end());ListNode* res = vec[0];ListNode* cur = vec[0];for (int i = 1; i < vec.size(); ++i) {cur->next = vec[i];cur = cur->next;}cur->next = NULL;return res;}
};