At the end of the exam, the average score of the class only got the second grade, the teacher in charge then asked: everyone knows the world’s first peak Qomolangma, anyone know the world’s second peak is what? Just as the teacher was going to continue to speak, he heard a voice in the corner: “K2”
preface
2018.11.11 punch in tomorrow’s topic: https://leetcode-cn.com/problems/sort-array-by-parity/
The title
Leetcode142 – A daily entry for finding links in lists https://leetcode-cn.com/problems/linked-list-cycle-ii/ link to https://leetcode.com/problems/linked-list-cycle-ii/ in English
Detailed questions
Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless. Note: Modification of a given linked list is not allowed. Advanced: Can you solve this problem without extra space?
The title,
The idea of using extra space
- If it doesn’t exist, insert the HashMap. If it does, the node is already inserted, so it’s a duplicate node. Why is it repeated?
code
1/ * *
2 * Definition for singly-linked list.
3 * class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {
7 * val = x;
8 * next = null;
9*}
10*}
11* /
12public class Solution {
13 public ListNode detectCycle(ListNode head) {
14 HashMap<ListNode,Integer> map = new HashMap<>();
15 if(head == null || head.next= =null)
16 return null;
17 while(head ! =null)
18 {
19 if(map.containsKey(head) == false)
20 {
21 map.put(head,1);
22 head = head.next;
23 }else{
24 return head;
25 }
26 }
27 return null;
28 }
29}
Copy the codeThe code on
- In lines 15-22, the hashMap determines if the node does not exist and inserts it into the HashMap.
- Lines 23-24, if this node exists in the HashMap, return this node, the entry node
The idea of not using extra space
- Use the fast and slow pointer, the fast pointer goes two steps each time, the slow pointer goes one step each time, if the fast and slow Pointers meet, there is a ring;
- After there is a ring, it is necessary to find the entry node of the ring. The node in a ring has been found, and the node is used to go through the loop. Since it is a ring, the node will definitely meet itself
- Know the length of the ring, and then reuse the thought of how fast a pointer, pointer quickly go first loop length, and then how a pointer together, such as pointer quickly walked the length of the ring first, when the two met must meet the entrance to a ring node (why? Because of how quickly a pointer will enter the ring, and due to the fast pointer walked the length of the ring first, so that is a cycle, So whenever you enter the ring, these two Pointers must meet.)
code
1/ * *
2 * Definition for singly-linked list.
3 * class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {
7 * val = x;
8 * next = null;
9*}
10*}
11* /
12public class Solution {
13 boolean flag = true;
14 public ListNode detectCycle(ListNode head)
15 {
16 ListNode pHead = head;
17 if(pHead == null || pHead.next= =null)
18 return null;
19 ListNode pNode = judgeHasChain(pHead);
20 if(pNode ! =null)
21 {
22 int lengthChain = 1;
23 ListNode pNodeCopy = pNode.next;
24 while(pNodeCopy ! = pNode)
25 {
26 lengthChain++;
27 pNodeCopy = pNodeCopy.next;
28 }
29 ListNode fast = pHead;
30 ListNode slow = pHead;
31 int temp = 0;
32 while(temp < lengthChain)
33 {
34 fast = fast.next;
35 temp++;
36 }
37 while(fast ! = slow)
38 {
39 fast = fast.next;
40 slow = slow.next;
41 }
42 return fast;
43 }
44 return null;
45 }
46 private ListNode judgeHasChain(ListNode pHead)
47 {
48 ListNode fast = pHead.next;
49 ListNode slow = pHead;
50 while(fast ! = slow)
51 {
52 if(fast ! =null && fast.next! =null)
53 {
54 fast = fast.next;
55 }else{
56 flag = false;
57 break;
58 }
59 if(slow ! =null && slow.next! =null)
60 {
61 slow = slow.next;
62 }else{
63 flag = false;
64 break;
65 }
66 if(fast == slow)
67 {
68 return fast;
69 }else{
70 fast = fast.next;
71 }
72 }
73 if(flag)
74 return fast;
75 return null;
76 }
77}
Copy the codeThe code on
- 46-76 is to determine whether there are rings in the linked list, which was discussed in detail in the previous article: http://t.cn/EANBcf4
- In line 19, if the list has a ring, the returned node must be in the ring
- Lines 22-28, using the nodes in line 19, iterate over the length of the calculation ring
- Line 32-36, the fast pointer goes the length of the ring first
- The 37-41 fast and slow Pointers go together, and when they meet, they are the entry nodes of the ring
conclusion
# 2018.11.11 clock
Author Chowgory experienced the autumn admission of 2019. He is a computer master of Harbin Institute of Technology and a Java engineer admitted to Baidu. Welcome to follow my wechat official account: The official account has 3T programming resources, and my friend and I (admitted baidu C++ engineer) prepared nearly 200 MB of required interview Java and C++ experience during the autumn recruitment, and there is a leetcode punch card group and technical exchange group every day, welcome to follow.