每天一道leetcode142-寻找链表中环的入口
- 2019 年 10 月 4 日
- 筆記
题目
每天一道leetcode142-寻找链表中环的入口 分类：链表 中文链接： https://leetcode-cn.com/problems/linked-list-cycle-ii/ 英文链接 https://leetcode.com/problems/linked-list-cycle-ii/
题目详述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 说明：不允许修改给定的链表。 进阶： 你是否可以不用额外空间解决此题？
题目详解
使用额外空间的思路
- 就是使用一个hashmap，去遍历一遍链表，每遍历一个链表，如果不存在这个节点，那么就插入hashmap，如果存在，说明这个节点已经插入了，那么这个节点就是重复的节点，为啥重复了，就是环的入口节点了。
代码
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { HashMap<ListNode,Integer> map = new HashMap<>(); if(head == null || head.next == null) return null; while(head != null) { if(map.containsKey(head) == false) { map.put(head,1); head = head.next; }else{ return head; } } return null; } }
代码讲解
- 15-22行，hashmap判断这个节点如果不存在，那么插入到hashmap里面；
- 23-24行，hashmap中存在这个节点，那么就返回这个节点，也就是入口节点
不使用额外空间的思路
- 使用快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针相遇说明有环；
- 有环以后，需要寻找环入口节点，已经找到了一个环的中的节点，利用这个节点，去往下遍历，由于是环，所以这个节点肯定会和自身相遇，相遇以后，记录相遇过程中走的步数，就是环的长度
- 知道环的长度以后，然后再利用快慢指针的思想，快指针先走环长度，然后快慢指针再一起走，这样因为快指针先走了环的长度，当两者相遇肯定是环的入口节点相遇（为啥呢，因为快慢指针肯定会进入环里面，而由于快指针先走了环的长度，所以也就是一个周期，所以只要进入环，那么这两个指针必然相遇）
代码
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { boolean flag = true; public ListNode detectCycle(ListNode head) { ListNode pHead = head; if(pHead == null || pHead.next == null) return null; ListNode pNode = judgeHasChain(pHead); if(pNode != null) { int lengthChain = 1; ListNode pNodeCopy = pNode.next; while(pNodeCopy != pNode) { lengthChain++; pNodeCopy = pNodeCopy.next; } ListNode fast = pHead; ListNode slow = pHead; int temp = 0; while(temp < lengthChain) { fast = fast.next; temp++; } while(fast != slow) { fast = fast.next; slow = slow.next; } return fast; } return null; } private ListNode judgeHasChain(ListNode pHead) { ListNode fast = pHead.next; ListNode slow = pHead; while(fast != slow) { if(fast != null && fast.next != null) { fast = fast.next; }else{ flag = false; break; } if(slow != null && slow.next != null) { slow = slow.next; }else{ flag = false; break; } if(fast == slow) { return fast; }else{ fast = fast.next; } } if(flag) return fast; return null; } }
代码讲解
- 46-76 就是判断链表中是否有环，之前有详细讲过 之前的文章链表：每天一道leetcode141-环形链表
- 19行中，如果链表有环，那么返回的这个节点必然在环中
- 22-28行，利用19行的节点，遍历计算环的长度
- 32-36行，快指针先走环长度
- 37-41行 快慢指针一起走，相遇就是环的入口节点
