0


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

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

题目来源:leetcode

1、问题描述

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
在这里插入图片描述

2、思路解析

思路:前后指针

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

3、代码实现

  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * ListNode *next;
  6. * ListNode() : val(0), next(nullptr) {}
  7. * ListNode(int x) : val(x), next(nullptr) {}
  8. * ListNode(int x, ListNode *next) : val(x), next(next) {}
  9. * };
  10. */
  11. class Solution {
  12. public:
  13. ListNode*removeNthFromEnd(ListNode* head,int n){//添加伪首节点
  14. ListNode*proot=new ListNode(-1);
  15. proot->next=head;
  16. ListNode*root=proot;//节点先到达链表的第n个节点while(n--){
  17. root=root->next;}
  18. ListNode*cur=proot;
  19. ListNode*pre=NULL;//等到节点root位NULL时cur就会到达节点的倒数的第n个节点while(root){
  20. root=root->next;
  21. pre=cur;
  22. cur=cur->next;}//删除节点
  23. pre->next=cur->next;//连接节点return proot->next;}};

环形链表

题目来源:leetcode

1、问题描述

在这里插入图片描述

2、思路解析

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

在这里插入图片描述

3、代码实现

  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * ListNode *next;
  6. * ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11. bool hasCycle(ListNode *head){if(head==NULL){return false;}
  12. unordered_set<ListNode*>s;while(head){if(s.find(head)!=s.end()){return true;}
  13. s.insert(head);
  14. head=head->next;}return false;}};
  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * ListNode *next;
  6. * ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11. bool hasCycle(ListNode *head){if(head==NULL){return false;}
  12. ListNode*begin=head;
  13. ListNode*end=head;while(end&&end->next){
  14. end=end->next->next;
  15. 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、代码实现

  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * ListNode *next;
  6. * ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11. ListNode *detectCycle(ListNode *head){if(head==NULL){returnNULL;}
  12. vector<ListNode*>s;while(head){if(find(s.begin(),s.end(),head)!=s.end()){return head;}
  13. s.push_back(head);
  14. head=head->next;}returnNULL;}};
  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * ListNode *next;
  6. * ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public://快慢指针
  11. ListNode *detectCycle(ListNode *head){if(head==NULL){returnNULL;}
  12. ListNode*begin=head;
  13. ListNode*end=head;//块指针一次走两步while(end&&end->next!=NULL){
  14. begin=begin->next;
  15. end=end->next->next;//快慢指针相遇if(begin==end){
  16. ListNode*node=head;while(node!=begin){
  17. node=node->next;
  18. begin=begin->next;}//找到入环得第一个节点return node;}}returnNULL;}};
标签: 算法 面试 链表

本文转载自: https://blog.csdn.net/qq_50408340/article/details/124617077
版权归原作者 自首的小偷 所有, 如有侵权,请联系我们删除。

“面试必刷算法TOP101之双指针篇 TOP 21”的评论:

还没有评论