面试必刷算法TOP101之双指针篇 TOP 21

删除链表的倒数第 N 个结点

题目来源：leetcode

1、问题描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

2、思路解析

思路：前后指针

（1）首先给链表添加伪首节点，这是防止删除节点是头节点，删除头节点后后边的节点就会丢失
（2）循环先到达使节点root从头节点开始链表的正数第n个节点
（3）节点cur从链表的头节点开始循环，直到节点root到达链表的尾部,记得保存删除节点的前一个节点
（4）删除cur节点即可

3、代码实现

/**
 * 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*removeNthFromEnd(ListNode* head,int n){//添加伪首节点
        ListNode*proot=new ListNode(-1);
        proot->next=head;
        ListNode*root=proot;//节点先到达链表的第n个节点while(n--){
            root=root->next;}
        ListNode*cur=proot;
        ListNode*pre=NULL;//等到节点root位NULL时cur就会到达节点的倒数的第n个节点while(root){
            root=root->next;
            pre=cur;
            cur=cur->next;}//删除节点
        pre->next=cur->next;//连接节点return proot->next;}};

环形链表

题目来源：leetcode

1、问题描述

2、思路解析

思路一：哈希
将节点地址存放在hash中每次检测hash检测有没有，如果在hash检测有同样的地址就证明这个链表存在环
思路二：快慢指针
（1）快慢指针（begin，end）同时从链表头节点开始出发
（2）快指针每次走两步，慢指针每次走一步
（3）当快指针走2n个节点时慢指针走了n个节点
（4）在某一时刻这俩个指针必定会相遇，并且快指针会超过慢指针
（5）所以当两个指针相遇时就说明这个链表存在环

3、代码实现

/**
 * 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){return false;}
       unordered_set<ListNode*>s;while(head){if(s.find(head)!=s.end()){return true;}
           s.insert(head);
           head=head->next;}return false;}};

/**
 * 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){return false;}
       ListNode*begin=head;
       ListNode*end=head;while(end&&end->next){
           end=end->next->next;
           begin=begin->next;//两个指针指向同一个节点if(begin==end){return true;}}return false;}};

环形链表Ⅱ

题目来源：leetcode

1、问题描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

2、思路解析

思路一：哈希
将节点地址存放在hash中每次检测hash检测有没有，如果在hash检测有同样的地址就直接返回节点地址
思路二：快慢指针

3、代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head){if(head==NULL){returnNULL;}
       vector<ListNode*>s;while(head){if(find(s.begin(),s.end(),head)!=s.end()){return head;}
           s.push_back(head);
           head=head->next;}returnNULL;}};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public://快慢指针
    ListNode *detectCycle(ListNode *head){if(head==NULL){returnNULL;}
        ListNode*begin=head;
        ListNode*end=head;//块指针一次走两步while(end&&end->next!=NULL){
            begin=begin->next;
            end=end->next->next;//快慢指针相遇if(begin==end){
                ListNode*node=head;while(node!=begin){
                    node=node->next;
                    begin=begin->next;}//找到入环得第一个节点return node;}}returnNULL;}};