数据结构之链表OJ练习检验你的链表水平是否合格
1.反转链表
K个一组翻转链表
链表的中间节点：
链表倒数第k个节点：
删除链表倒数第k个节点：
合并两个有序链表：
链表插入排序：
链表排序：
删除链表的节点：
删除链表的节点II：
环形链表（重点面试常考）
环形链表Il（重点面试常考）
分割链表：
回文链表：
链表相交：
1.反转链表
对应letecode链接：
力扣
https://leetcode-cn.com/problems/UHnkqh/
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
注意：本题与主站 206 题相同： https://leetcode-cn.com/problems/reverse-linked-list/
解题分析： 方法1，双指针法:
设置两个链表：ans 表示已经被反转的链表, head 表示还未被反转的链表。
遍历链表，每次将未被反转的链表 head 的 首元节点反转，直至未被反转的链表为空。
对应代码：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode*ans=nullptr;
while(head){
ListNode*restList =head->next;//保存head的下一个节点
head->next=ans;//翻转指针
ans=head;//迭代
head=restList;
}
return ans;
}
};运行结果：
方法二：递归
思想与上面的思想大致相同，翻指针：
1.使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
2.此后，每次函数在返回的过程中，让当前结点的下一个结点的 next->next 指针指向当前节点。
3.同时让当前结点的 next->next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
4.当递归函数全部出栈后，链表反转完成。
图解：
对应代码：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head||!head->next)return head;
ListNode*ret=reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return ret;
}
};方法三：头插法
1.原链表的头结点就是反转之后链表的尾结点，使用 head 标记 .
2.定义指针 cur，初始化为 head .
3.每次都让 head 下一个结点的 next 指向 cur ，实现一次局部反转
4.局部反转完成之后，cur和 head 的 next 指针同时 往前移动一个位置
5.循环上述过程，直至 cur 到达链表的最后一个结点 。
对应代码：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) { return NULL; }
ListNode* cur = head;
while (head->next != NULL) {
ListNode* t = head->next->next;
head->next->next = cur;
cur = head->next;
head->next = t;
}
return cur;
}
};递归写法太复杂在这里就不写了：
K个一组翻转链表
对应letecode链接：
25. K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 3：
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例 4：
输入：head = [1], k = 1
输出：[1]
提示：
列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz
相信有了上面那两道题的基础这道题就每这么难了：
解题思路：
我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。
接下来的问题就是如何翻转一个分组内的子链表。翻转一个链表并不难，过程可以参考上面的翻转链表。但是对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表链接，以及子链表的尾部与下一个子链表链接。如下图所示：
对应代码：
翻转[head,tail）区间的链表：
ListNode*Reverse(ListNode*head,ListNode*tail)//翻转区间[head,tail)不包括tail
{
ListNode*cur=head;
ListNode*prev=nullptr;
while(cur!=tail){
ListNode*next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
return prev;
}总代码：
class Solution {
public:
ListNode*Reverse(ListNode*head,ListNode*tail)//翻转区间[head,tail)不包括tail
{
ListNode*cur=head;
ListNode*prev=nullptr;
while(cur!=tail){
ListNode*next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
return prev;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if(!head||!head->next)return head;//空或者只有一个元素了则返回
ListNode*tail=head;
for(int i=0;i<k;i++){
if(!tail)//不足k个
return head;
tail=tail->next;
}
ListNode*newnode=Reverse(head,tail);//翻转每一组链表
head->next=reverseKGroup(tail,k);//翻转之后head已经变成了尾节点了
return newnode;//翻转完之后返回
}
};这道题和两两一组翻转链表是一样的：
对应链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/https://leetcode-cn.com/problems/swap-nodes-in-pairs/
https://leetcode-cn.com/problems/swap-nodes-in-pairs/
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
由于上图已经讲过思路在这里就不赘述了：
class Solution {
public:
ListNode*Reverse(ListNode*head,ListNode*tail){
ListNode*cur=head;
ListNode*prev=nullptr;
while(cur!=tail){
ListNode*next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
return prev;
}
ListNode* swapPairs(ListNode* head) {
if(!head||!head->next)return head;
ListNode*tail=head;
for(int i=0;i<2;i++){
if(!tail)return head;
tail=tail->next;
}
ListNode*newnode=Reverse(head,tail);
head->next=swapPairs(tail);
return newnode;
}
};
当然还可以采用另外一种递归方式：
1.递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。
2.如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。
3.用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。
对应代码：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
};链表的中间节点：
对应letecode链接：
876. 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
解题思路：快慢指针
1.用两个指针 slow 与 fast 一起遍历链表。
2.slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间位置。
3.注意链表的长度有可能是偶数或者奇数，所以循环结束的条件为fast!=nullptr&&fast->next!=nullptr;
对应代码：
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode*fast=head;
ListNode*slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
};提交结果：
l
链表倒数第k个节点：
对应letecode 链接：
题目描述：
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
解题思路：快慢指针
1.定义一个快指针先让它走k步
2.定义一个慢指针指向链表的头节点，此时和fast同时走。
3.结束条件,当fast走到空了就结束了，此时slow只是倒数第k个节点
对应代码：
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode*fast=head;
for(int i=0;i<k;i++){
if(fast)fast=fast=fast->next;//防止链表的长度不够走
}
ListNode*slow=head;
while(fast){
fast=fast->next;//同时走
slow=slow->next;
}
return slow;
}
};删除链表倒数第k个节点：
对应letecode链接：
剑指 Offer II 021. 删除链表的倒数第 n 个结点 - 力扣（LeetCode） (leetcode-cn.com)
解题思路：快慢指针
1.这题与上题思路大致相同，只是本题是要删除倒数第k个节点，而上题是只要我们找到倒数第k个节点。
2.同样的我们可以 定义fast,slow指针先让fast指针先走K+1部，在让slow和fast同时走但是，循环结束之后我们要删除的刚好是slow的位置，那么我们就必须知道slow的前一个让后在将slow指向的节点删除，返回头节点即可
但是如果我们考虑特殊情况：
考虑一种比较特殊的情况，若需要删除的就是头节点，这时候就存在 bug 。如上图中快指针先走了 6 步，这时候已经超出了尾节点，所以对于这种情况需要做 if 特殊判断。一种比较好的避免这种特殊判断的方法是引入哨兵节点 dummy，该结点的 next 指针指向头指针，之后这样处理以 dummy 为头结点的链表就可以规避上述问题，最后返回dummy 的 next 指针所指的链点就是需要的结果。以 3 个结点的链表处理删除头结点的情况为例子，如下图（红色节点为哨兵节点）
对应代码：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode*dummyHead=new ListNode(-1);
dummyHead->next=head;
ListNode*fast=head;
for(int i=0;i<k;i++){//让快指针走k步
if(fast)fast=fast->next;
}
ListNode*slow=dummyHead;
while(fast){
fast=fast->next;
slow=slow->next;
}
ListNode*del=slow->next;
slow->next=slow->next->next;
delete del;//删除节点
ListNode*ans=dummyHead->next;//保存头节点
delete dummyHead;//释放哑节点
return ans;
}
};运行结果：
合并两个有序链表：
对应letecode链接：
21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/merge-two-sorted-lists/
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
解题思路：
1.我们可以定义一个哑节点prevHead。
2.假设两个链表分别为l1,和l2，变量l1和l2，去它们之中小的那个尾插到哑节点（prevHead)后面，在将对应链表中的节点向后移一位 .
3.当循环结束之后l1和l2中有一个链表的节点取完了但是我们不知道是那一个节点走完了，但是我们可以都判断一个，将其链接到新链表的尾步即可。
4.同时我们还需要定义一个prev来记录新链表的头，代替哑节点走上述的过程
对应图解：
对应代码：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode*prevHead=new ListNode(-1);
ListNode*prev=prevHead;
while(l1&&l2){
if(l1->val<=l2->val){
prev->next=l1;
prev=prev->next;
l1=l1->next;
}
else{
prev->next=l2;
prev=prev->next;
l2=l2->next;
}
}
if(l1)prev->next=l1;
if(l2)prev->next=l2;
return prevHead->next;
}
};运行结果：
链表插入排序：
对应letecode链接：
力扣
https://leetcode-cn.com/problems/insertion-sort-list/
题目描述：
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
解题思路：
如果对插入排序不太理解的铁子，可以看一下我写的排序的博客
对应链接：
1.链表与数组的插入排序不同，数组支持随机访问。而链表是不支持随机访问的。我们在数组中可以随意的前后移动，将指针指向值和新元素的值比较后，将新元素插入到合适的位置。我们知道链表查询元素的时间复杂度为 O（n）,我们只能够通过遍历链表查询元素。那么我们怎么才能将新元素放到合适的位置呢？
此时我们不能通过移动绿色指针来寻找 5 的合适位置，那么我们应该怎么做了？
当我们发现绿色指针的值大于新元素时（7 > 5），我们则可以定义一个新指针，让其从哑节点开始遍历，直到找到新元素（5）的位置，（4 和 7 之间），然后再将新元素插入即可
通过上面的分析我们知道了大致过程，那么我们的是如何将新元素插入到指定位置的呢？
我们想要将 3 插入到 2 和 4 的中间，此时我们三个指针分别指向 2，4，3
我们共分 4 步，来完成这个操作，见下图
完成上述操作之后链表就变成了：
对应代码:
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(!head||!head->next)return head;//如果只有一个元素或者链表为空则返回head
ListNode*dummyNode=new ListNode(-1);//定义哑节点
dummyNode->next=head;
ListNode*prev=head->next;
ListNode*last=head;
ListNode*temphead=dummyNode;
while(prev){
if(last->val<=prev->val){
last=last->next;
prev=prev->next;
continue;
}
temphead=dummyNode;
while(temphead->next->val<=prev->val){//比较找到对应的位置
temphead=temphead->next;
}
//找到了对应的插入位置，如果不清除的老铁可以自己画一下图
last->next=prev->next;
prev->next=temphead->next;//链接
temphead->next=prev;
prev=last->next;//迭代往后走
}
return dummyNode->next;
}
};当然我们也可以不用头节点，但是那样就可以复杂一些：在这里就简单的改成代码不过多的解释：
链表排序：
对应letecode链接：
[Alton]-148-桶/归并 3 解 Java/C++ - 排序链表 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/sort-list/
题目描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
解题思路：归并排序
归并排序，逃脱不了，分合。 思路如下：
分割 -> 通过递归不断分割链表，在此过程中需要保证链表不丢失的情况下，不断想下切割 （e.g. 8 -> 4 -> 2）
关键在于找到链表的中心点， 并从中心点将链表分割成 2 部分。
我们可以使用经典的快慢双指针链表分割方法，其中有个点需要注意，链表长度为奇偶，切割处理方式是不同的，这里根据大家喜欢的方式处理即可，这里没有明确规定必须使用什么切割方式，笔者的切换策略如下：
快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
找到中点后，将链表进行断开，将当前链表分成 2 部分
对两个链表分别排序
慢指针的下一节点，指向空即可
分割阶段结束 -> 递归退出 -> 直到分割的链表长度为 1
此时递归到底了
merge 环节，退出递归的过程中，不断的排序合并
merge 节点其实包含在分割阶段里边
merge -> 排序当前链表
对应代码：
分割代码：
ListNode*splitListNode(ListNode*head){
if(!head||!head->next)return head;
ListNode*slow=head;
ListNode*fast=head;
ListNode*prev=nullptr;
while(fast&&fast->next){
prev=slow;
fast=fast->next->next;
slow=slow->next;
}
return prev;
}注意中间那个节点要分给对二段链表：
如果只有两个节点的话，slow指向的就是第二个节点。如果将其分给第一个合并的链表那么就会死循环！！！！
合并链表：
istNode*mergeListNode(ListNode*head1,ListNode*head2){
ListNode*dummyHead=new ListNode(-1);
ListNode*ans=dummyHead;
while(head1&&head2){
if(head1->val<=head2->val){
ans->next=head1;
ans=ans->next;
head1=head1->next;
}
else{
ans->next=head2;
ans=ans->next;
head2=head2->next;
}
}
if(head1)ans->next=head1;
if(head2)ans->next=head2;
return dummyHead->next;
}由于上面的之前都已经讲解过了在这里就不重复了：
总代码：
class Solution {
public:
ListNode*splitListNode(ListNode*head){
if(!head||!head->next)return head;
ListNode*slow=head;
ListNode*fast=head;
ListNode*prev=nullptr;
while(fast&&fast->next){
prev=slow;
fast=fast->next->next;
slow=slow->next;
}
return prev;
}
ListNode*mergeListNode(ListNode*head1,ListNode*head2){
ListNode*dummyHead=new ListNode(-1);
ListNode*ans=dummyHead;
while(head1&&head2){
if(head1->val<=head2->val){
ans->next=head1;
ans=ans->next;
head1=head1->next;
}
else{
ans->next=head2;
ans=ans->next;
head2=head2->next;
}
}
if(head1)ans->next=head1;
if(head2)ans->next=head2;
return dummyHead->next;
}
ListNode* sortList(ListNode* head) {
if(!head||!head->next)return head;
ListNode*mid=splitListNode(head);
ListNode*midNext=mid->next;
mid->next=nullptr;
ListNode*head1=sortList(head);
ListNode*head2= sortList(midNext);
return mergeListNode(head1,head2);
}
};运行结果：
当然这题还可以使用快速排序的前后指针法进行排序：
我们可以选取头节点作为基准值，遍历链表，将比它小的节点头插在它前面，比它大的节点尾插在它后面
假设lhead维护的是小于基准值的头插指针，utail维护的是大于等于基准值的尾插指针
则一次对[head , end）快排结束后有
-[ lhead , head ) （左闭右开）是小于基准值的一部分
-[ head.next , end ) （左闭右开）是大于等于基准值的一部分
再分治这两部分即可
对应代码:s
class Solution {
public:
ListNode* sortList(ListNode* head) {
return quickSortListNode(head,nullptr);
}
ListNode*quickSortListNode(ListNode*head,ListNode*end){
if(head ==end || head->next ==end) return head;
ListNode* lhead = head ,*utail = head ,*p = head->next;
while (p != end){
ListNode *next = p->next;
if(p->val < head->val){//头插
p->next = lhead;
lhead = p;
}
else { //尾插
utail->next = p;
utail = p;
}
p = next;
}
utail->next = end;
ListNode *node = quickSortListNode(lhead, head);
head->next = quickSortListNode(head->next, end);
return node;
}
};删除链表的节点：
对应letecode链接：
剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
解题思路：
题中说了链表中的节点值互不相同，也就是说最多只能删除一个。最简单的一种方式就是双指针求解，我们使用两个指针一个指向当前的节点，一个指向当前的上一个节点。
对应代码：
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode*dummyListNode=new ListNode(-1);
ListNode*prev=dummyListNode;
dummyListNode->next=head;
ListNode*cur=head;
while(cur){
if(cur->val==val){
prev->next=cur->next;//删除节点
cur=cur->next;
break;
}
else{
cur=cur->next;
prev=prev->next;//同时往后走
}
}
ListNode*ans=dummyListNode->next;//保存答案
delete dummyListNode;
return ans;
}
};对应运行结果：
删除链表的节点II：
对应letecode链接：
82. 删除排序链表中的重复元素 II - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排序
解题思路：
题目与上题的不同之处是，删除所有重复出现的元素。如示例所示，头结点是1，其后结点和其重复，因此也要删除。这时，用解决上题题的思路就不合适了。
因此，需要一个虚拟头结点，然后用变量prev指向该虚拟头结点。这样在删除重复结点之后，剩余的结点就可以挂在prev之后继续考察了。具体步骤我们一起看下。
为了方便演示，我将示例给出的链表删减如下：
然后变量difNode指向cur所指向的结点，用以记录和当前考察结点不同的结点位置。
变量curRepeatNum表示和变量cur指向的结点重复的结点个数，初始值为0
这时，变量cur和变量difNode指向的是同一个结点，因此curRepeatNum=1。
接着，将变量difNode向后移动一个位置，看下一个结点和变量cur指向的结点值是否相等。在这里，变量cur和变量difNode指向的结点值相等，因此curRepeatNum=2。
接着，将变量difNode继续向后移动一个位置，看下一个结点和变量cur指向的结点值是否相等。在这里，变量cur和变量difNode指向的结点值不相等。
时curRepeatNum=2，表示cur指向的结点1在链表中出现了2次。接着要做的是将变量prev指向的结点的后继指针指向变量difNode所指向的结点。这样，将就重复结点1从链表中删除了。
最后，要做的是将变量cur指向difNode所指向的结点，进行下一个结点的去重
对应代码：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode*dummyHead=new ListNode(-1);
dummyHead->next=head;
ListNode*prev=dummyHead;
ListNode*cur=head;
while(cur){
int curRepeatNum=0;
ListNode*difNode=cur;// 找到和cur指向的结点值不同的结点
while(difNode&&difNode->val==cur->val){
curRepeatNum++;
difNode=difNode->next;
}
if(curRepeatNum>1){// 如果curRepeatNum的值大于1，则表示cur指向的结点重复出现了
prev->next=difNode;
}
else{
prev=cur;// cur指向的结点没有重复出现，则将变量prev指向cur所指向的结点
}
cur=difNode;
}
return dummyHead->next;
}
};运行结果：
环形链表（重点面试常考）
对应letecode链接：
141. 环形链表 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/linked-list-cycle/
题目描述：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
示例 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 或者链表中的一个 有效索引 。
解题思路：快慢指针：
最简单的一种方式就是快慢指针，慢指针每次走一步，快指针每次走两步，如果相遇就说明有环，如果有一个为空说明没有环。代码比较简单：
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode*fast=head;
ListNode*slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(slow==fast)return true;
}
return false;
}
};但是如果这道题是在面试中就不会这么容易让你过，因为太简单：面试官一般都会问你为什么他们一定会相遇，fast每次只能走两步吗？一次走三步走四步行不行，或者走n步行不行
答案是fast每次走两步才能保证他们一定会相遇 待博主细细道来：
假如环的长度是m，快慢指针最近的间距是n，如图所示
快指针每次走两步，慢指针每次走一步，所以每走一次快慢指针的间距就要缩小一步，他们之间的间距没走一次缩小1步由于m,n都是整数那么迟早都会减到0.
在图一中当走n次的时候就会相遇，在图二中当走m-n次的时候就会相遇。
那如果fast每次走三步了？还会不会相遇了？答案是不一定？
还是一样的当slow进环之后，假设他们的间距为n,但是fast,slow每走一次距离会缩小2，此时如果n是偶数那么它们会相遇，如果是奇数，那么他们之间的距离会减到-1，-1代码什么意思了？-1代码fast反超slow此时他们之间的距离就变成了环的长度减1，也就是m-1，和上面的分析一样，如果m-1是偶数那么就可以相遇当时如果m-1是奇数那么它又会减到-1，那么就会重复上述步骤。那么他们也就永远不会相遇。
fast一次走四步的分析方法也是类似的，各位铁子可以自己下去推导
环形链表Il（重点面试常考）
对应letecode链接：
142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)
对应题目描述：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
解题思路：双指针
1.设slow fast 第一次相遇 。设两指针 fast，slow 指向链表头部 head，fast 每轮走 2 步，slow 每轮走 11步。
第一种情况：
fast 指针走过链表末端，说明链表无环，直接返回 null；
第二种情况：若有环，两指针一定会相遇。因为每走 1 轮，fast 与 slow 的间距 -1，fast 终会追上 slow
第三种情况：
当fast == slow时， 两指针在环中 第一次相遇 。下面分析此时fast 与 slow走过的 步数关系 ：
设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点（注意：a 和 b 是未知数，例如图解上链表 a=4 , b=5）。
设两指针分别走了 f，s 步，则有：
fast 走的步数是slow步数的 2 倍，即 f = 2s；（解析： fast 每轮走 2 步）
fast 比 slow多走了 n 个环的长度，即f=s+nb；（ 解析： 双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走 环的长度整数倍 ）；
以上两式相减得：
f = 2nb，s = nb，即fast和slow 指针分别走了 2n，n 个 环的周长 （注意： n 是未知数，不同链表的情况不同）。
如果让指针从链表头部一直向前走并统计步数k，那么所有 走到链表入口节点时的步数 是：k=a+nb（先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）。
而目前，slow 指针走过的步数为 nbnb 步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口。
但是我们不知道 a 的值，该怎么办？依然是使用双指针法。我们构建一个指针，此指针需要有以下性质：此指针和slow 一起向前走 a 步后，两者在入口节点重合。那么从哪里走到入口节点需要 a 步？答案是链表头部head。
双指针第二次相遇：
slow指针 位置不变 ，将fast指针重新 指向链表头部节点 ；slow和fast同时每轮向前走 1 步；
TIPS：此时 f = 0，s = nb ；
当 fast 指针走到f = a步时，slow 指针走到步s = a+nb，此时 两指针重合，并同时指向链表环入口 。
返回slow指针指向的节点。0
对应代码：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode*fast=head;
ListNode*slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(slow==fast){
fast=head;
while(fast!=slow){
fast=fast->next;
slow=slow->next;
}
return slow;
}
}
return NULL;
}
};分割链表：
对应letecode链接：
面试题 02.04. 分割链表 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2
输入：head = [2,1], x = 2
输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
解题思路：
只需要遍历链表的所有节点，小于x的放到一个小的链表中，大于等于x的放到一个大的链表中，最后再把这两个链表串起来即可。
对应代码：
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode*smallHead=new ListNode(-1);
//小链表的头
ListNode*bigHead=new ListNode(-1);
// 大链表的头
ListNode*smallTail=smallHead;
//小链表的尾
ListNode*bigTail=bigHead;
//大链表的尾
//变量链表
while(head){
if(head->val<x){
smallTail->next=head;//链接
smallTail=smallTail->next;
}
else{
bigTail->next=head;
bigTail=bigTail->next;//链接
}
head=head->next;
}
smallTail->next=bigHead->next;
bigTail->next=nullptr;//防止成环
return smallHead->next;
}
};运行结果：
回文链表：
对应letecode链接：
力扣
题目描述:
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
提示：
链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9
进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路：基本步骤上面都已经做过了
把链表分成前后两段，当链表节点数为奇数时，前半段要比后半段多一个节点；
把链表的后半段进行反转；
判断前半段链表和反转后的链表各节点值是否相同。若前半段比后半段多一个节点，多出的节点不做判断。
判断的时候使用两个指针指向前后段的头节点，逐各对比，直至指针 p2 为空。
对应代码：
反转代码：
ListNode*Reverse(ListNode*head)
{
iF(!head||!head->next)return head;
ListNode* res=Reverse(head->next);
head->next->next=head;
head->next=nullptr;
return res;
}分割链表的代码：
ListNode*GetMid(ListNode*head)
{
ListNode*prev=nullptr;
ListNode*slow=head;
ListNode*fast=head;
while(fast&&fast->next)
{
prev=slow;
fast=fast->next->next;
slow=slow->next;
}
prev->next=nullptr;
return slow;
}bool isPalindrome(ListNode* head) {
if(head==nullptr||head->next==nullptr)
return true;
ListNode*P2=GetMid(head);
P2=Reverse(P2);
ListNode*P1=head;
while(P2&&P1){
if(P1->val!=P2->val){
return false;
}
P1=P1->next;
P2=P2->next;
}
return true;
}
};总代码：
class Solution {
public:
ListNode*GetMid(ListNode*head)
{
ListNode*prev=nullptr;
ListNode*slow=head;
ListNode*fast=head;
while(fast&&fast->next)
{
prev=slow;
fast=fast->next->next;
slow=slow->next;
}
prev->next=nullptr;
return slow;
}
ListNode*Reverse(ListNode*head)
{
if(!head||!head->next)return head;
ListNode* res=Reverse(head->next);
head->next->next=head;
head->next=nullptr;
return res;
}
bool isPalindrome(ListNode* head) {
if(head==nullptr||head->next==nullptr)
return true;
ListNode*P2=GetMid(head);//将链表一分为二
P2=Reverse(P2);//反转后半段链表
ListNode*P1=head;
while(P2&&P1){
if(P1->val!=P2->val){//一一比较
return false;
}
P1=P1->next;
P2=P2->next;
}
return true;
}
};链表相交：
对应letecode链接：
面试题 02.07. 链表相交 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
解题思路：双指针
我们还可以使用两个指针，最开始的时候一个指向链表A，一个指向链表B，然后他们每次都要往后移动一位，顺便查看节点是否相等。如果链表A和链表B不相交，基本上没啥可说的，我们这里假设链表A和链表B相交。那么就会有两种情况，
一种是链表A的长度和链表B的长度相等，他们每次都走一步，最终在相交点肯定会相遇。
一种是链表A的长度和链表B的长度不相等，如下图所示：
虽然他们有交点，但他们的长度不一样，所以他们完美的错开了，即使把链表都走完了也找不到相交点。
我们仔细看下上面的图，如果A指针把链表A走完了，然后再从链表B开始走到相遇点就相当于把这两个链表的所有节点都走了一遍，同理如果B指针把链表B走完了，然后再从链表A开始一直走到相遇点也相当于把这两个链表的所有节点都走完了
所以如果A指针走到链表末尾，下一步就让他从链表B开始。同理如果B指针走到链表末尾，下一步就让他从链表A开始。只要这两个链表相交最终肯定会在相交点相遇，如果不相交，最终他们都会同时走到两个链表的末尾，我们来画个图看一下：
从上面之中我们可以知道：A指针和B指针如果一直走下去，那么他们最终会在相交点相遇，最后
代码实现：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode*tempA=headA;
ListNode*tempB=headB;
while(tempA!=tempB){
//如果指针tempA不为空，tempA就往后移一步。
//如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
tempA=(tempA==nullptr?headB:tempA->next);
tempB=(tempB==nullptr?headA:tempB->next);
}
return tempA; //tempA要么是空，要么是两链表的交点
}
};其实本题还又另外一种思路就是：
统计两个链表的长度，找到两个链表长的那个，让后让长的那个先走两个链表长度的绝对值之差的长度，然后在同时遍历链表，看是不是有节点相等，如果有则返回相同时的指针，如果遍历完了还没有找到相等的就返回nullptr,各位铁子们可以下去自己试一下
各位大佬动动你们的小手给博主点个赞！谢谢
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_56999918/article/details/121480160
内容来源于网络，如有侵权，请联系作者删除！
